Семинары (1171138), страница 4
Текст из файла (страница 4)
Красикова. — 2-е изд. — М.: Вильямс, 2005.— 1296 с.3. Дейтел Х. М. Как программировать на С++: Пер. с англ. – М.: ЗАО «ИздательствоБИНОМ», 2000 г. – 1024 с.: ил.4. Страуструп Б. Язык программирования С++. Специальное издание: ++: Пер. с англ. –М.: ЗАО «Издательство БИНОМ», 2008 г. – 1104 с. :ил.5. Шилдт Г. Полный справочник по С++: ++: Пер. с англ. – М.: Изд-во Вильямс, 2007 г.– 800 с.: ил.6. Шилдт Г. С++: Базовый курс: ++: Пер. с англ. – М.: Изд-во Вильямс, 2008 г.
– 624 с.:ил.6датаОтчет по лабораторной работе №5«Методы сортировки массивов, понятие сложности алгоритма»ОценкаБонус заподпись(max 5)сложностьЦели работы:Изучение основных методов сортировки массивов. Понятие сложности алгоритма напримере методов сортировки массивов.Задачи работы:-ознакомиться с методами сортировки массивов-написание программ сортировки массивовЗадание повышенной сложности (бонус за сложность – 10 баллов):Реализовать многофайловую программу: : в заголовочном файле определить необходимыепеременные и заголовки функций, во втором файле должен располагаться код функцийсортировки, в главном файле – вызов функции main.Краткий конспект теоретической части (ответы на контрольные вопросы)Сортировка массива методом пузырька____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Сортировка массива методом отбора__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Сортировка массива методом вставки ___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Сортировка массива методом Шелла_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Быстрая сортировка _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Сложность алгоритмов ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________1Методы сортировки массивов, понятие сложности алгоритмаПример 1: Сортировка массива методом пузырькаИдея метода состоит в сравнении двух соседних элементов, в результате чего меньшее число (болеелегкий "пузырек") перемещается на одну позицию влево.
Обычно просмотр организуют с конца, и послепервого прохода самое маленькое число перемещается на первое место. Затем все повторяется от концамассива до второго элемента и т.д.void bubble(int *x, int n){ register int i,j;int tmp;for(i=1;i<n;i++)for(j=n-1;j>=i; j--)if(x[j-1]>x[j]){ tmp=x[j-1]; x[j-1]=x[j]; x[j]=tmp; }}Задание 1:написать программу реализующую сортировку массива методом пузырька.
Представитьблок схему алгоритма.Тестовые данныеРезультат выполненияПример 2: Сортировка массива методом отбораИдея метода: находится элемент с наименьшим значением и меняется местами с первым элементом.Среди оставшихся элементов ищется наименьший, который меняется со вторым и т.д.
Функция select,реализующая такую процедуру, приведена ниже:void select(int *x, int n){ register int I,j,k;int q,tmp;for(i=0; i<n-1;i++){ q=0; k=I; tmp=x[i];for(j=i+1; j<n; j++){ if(x[j]<tmp){ k=j; tmp=x[j]; q=1; }}if(q) { x[k]=x[i]; x[i]=tmp; }}}2Задание 2:написать программу реализующую сортировку массива методом отбора. Представитьблок схему алгоритма.Тестовые данныеРезультат выполненияПример 3: Сортировка массива методом вставкиИдея метода: последовательное пополнение ранее упорядоченных элементов. На первом шагесортируются два первые элемента. Затем на свое место среди них вставляется третий элемент. К тремупорядоченным добавляется четвертый, который занимает свое место в четверке и т.д.
Функция insert,реализующая описанную процедуру, приведена ниже:void insert(int *x, int n){ register int i,j;int tmp;for(i=1;i<n;i++){ tmp=x[i];for(j=i-1;j>=0 && tmp<x[j]; j--)x[j+1]=x[j];x[j+1]=tmp;}Задание 3:написать программу реализующую сортировку массива методом вставки. Представитьблок схему алгоритма.Тестовые данныеРезультат выполнения3Пример 4: Сортировка массива методом ШеллаВ 1959 году сотрудник фирмы IBM D.L. Shell предложил оригинальный алгоритм сортировки. Поего предложению сначала сортируются элементы, отстоящие друг от друга на 3 позиции, затем – на двепозиции и, наконец, сортируются смежные элементы. В дальнейшем экспериментальным путем былинайдены более удачные расстояния между сортируемыми элементами: 9 5 3 2 1. Среднее времяработы усовершенствованного алгоритма Шелла порядка n1.2.
Это существенно лучше, чем характерная длятрех предыдущих методов величина порядка n2.void shell(int *x, int n){ register int i,j,gap,k;int xx;char a[5]={9,5,3,2,1};for(k=0;k<5;k++){ gap=a[k];for(i=gap;i<n;i++){ xx=x[i];for(j=i-gap; xx<x[j] && j>=0; j=j-gap)x[j+gap]=x[j];x[j+gap]=xx;}}}Задание 4:написать программу реализующую сортировку массива методом Шелла. Представитьблок схему алгоритма.Тестовые данныеРезультат выполненияПример 5: быстрая сортировкаИзвестный математик C.A.R.
Hoare в 1962 году опубликовал алгоритм быстрой сортировки, закоторым закрепилось название quicksort. Основная идея быстрой сортировки напоминает метод поискаделением пополам. Сначала выбирается граничный элемент в сортируемом массиве, его называюткомпарандом. Все, что больше этого элемента переносится в правую часть массива, а все, что меньше – влевую. После первого шага средний элемент оказывается на своем месте. Затем аналогичная процедураповторяется для каждой половины массива. На каждом последующем шаге размер обрабатываемогофрагмента массива уменьшается вдвое.
Количество операций, которое требуется для реализации этойпроцедуры, оценивается константой n*log 2 n. Это еще быстрее, чем сортировка Шелла. В отличие отпредыдущих функций быстрая сортировка оформлена из двух функций – quick, которая допускает принятоев других функциях обращение, и рекурсивной процедуры qs:void quick(int *x, int n)4{ qs(x,0,n-1); }//---------------------------------void qs(int *x,int left,int right){ register int i,j;int xx,tmp;i=left; j=right;xx=x[(left+right)/2];do { while(x[i]<xx && i<right)i++;while(xx<x[j] && j>left) j--;if(i<=j){ tmp=x[i]; x[i]=x[j];x[j]=tmp; i++; j--;}}while(i<=j);if(left<j) qs(x,left,j);if(i<right)qs(x,i,right);}Здесь функция quick(int *x, int n) задает вызов основной сортиру.щей функции qs(int *x,int left,int right).Среднее число выполняемых сравнений равно: n*log n.
Среднее количество перестановок приблизительноравно: (n*log n)/6. Эти показатели существенно меньше, чем у рассмотренных выше методов сортировки.Следует иметь в виду, если значение-компаранд для каждого из разделов является максимальным, то напрактике метод быстрой сортировки вырождается в метод «медленной» сортировки с временем выполнения,пропорциональным квадрату количества элементов.Задание 5:написать программу реализующую сортировку массива методом быстрой сортировки.Представить блок схему алгоритма.Тестовые данныеРезультат выполненияСложность алгоритмов:алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:• Время — основной параметр, характеризующий быстродействие алгоритма.
Называется такжевычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведениеалгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётсямножество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — этоO(n*log(n)) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n).Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегдануждаются по меньшей мере в Ω(n*log(n)) сравнениях. Тем не менее, существует алгоритмсортировки Хана (Yijie Han) с вычислительной сложностью O(n*log(log(n))*log(log(log(n)))),использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за Ообозначением скрывается весьма большой коэффициент, что делает невозможным его применение вповседневной практике).
Также существует понятие сортирующих сетей. Предполагая, что можно5•одновременно (например, при параллельном вычислении) проводить несколько сравнений, можноотсортировать n чисел за O(log2(n)) операций. При этом число n должно быть заранее известно;Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранениеданных. Как правило, эти алгоритмы требуют O(log(n)) памяти. При оценке не учитывается место,которое занимает исходный массив и независящие от входной последовательности затраты,например, на хранение кода программы.Представление кода программы в нескольких файлахПредставим себе, что компоненты программы имеют существенно большие размеры, и зададимсявопросом, как в этом случае распределить их по нескольким файлам.
Программу main поместим в файл,который мы назовем main.с; функции push, pop и их переменные расположим во втором файле, stack.с; aфункцию getop - в третьем, getop.c. Наконец, функции getch и ungetch разместим в четвертом файле getch.с;мы отделили их от остальных функций.Существует еще один момент, о котором следует предупредить, - определения и объявлениясовместно используются несколькими файлами. Нужно, насколько это возможно, централизовать этиобъявления и определения так, чтобы для них существовала только одна копия. Тогда программу в процессеее развития будет легче и исправлять, и поддерживать в нужном состоянии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
