Лекции (1171139), страница 12
Текст из файла (страница 12)
Вычислить скалярное произведения двух векторов.41Сложность алгоритмов.Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когдаэлемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки.На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные,никак не влияющие на работу алгоритма. Нам уже известно, что правильность - далеко не единственноекачество, которым должна обладать хорошая программа. Одним из важнейших является эффективность,характеризующая прежде всего время выполнения программы T(n) для различных входных данных(параметра n).Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использованияпамяти:••Время — основной параметр, характеризующий быстродействие алгоритма.
Называется такжевычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведениеалгоритма в терминах мощности входного множества 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)))),использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за Ообозначением скрывается весьма большой коэффициент, что делает невозможным его применение вповседневной практике).
Также существует понятие сортирующих сетей. Предполагая, что можноодновременно (например, при параллельном вычислении) проводить несколько сравнений, можноотсортировать n чисел за O(log2(n)) операций. При этом число n должно быть заранее известно;Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранениеданных.
Как правило, эти алгоритмы требуют O(log(n)) памяти. При оценке не учитывается место,которое занимает исходный массив и независящие от входной последовательности затраты,например, на хранение кода программы.Методы сортировки массивовСортировка числовых и нечисловых данных – одна из важнейших процедур обработки информации,т.к. она существенно ускоряет последующий поиск тех или иных объектов. О том, какое внимание уделяетсяразличным алгоритмам сортировки, свидетельствует специальный том Д.Кнута "Искусствопрограммирования для ЭВМ: Сортировка и поиск" объемом порядка 840 стр. Надо отметить, что оценкатрудоемкости различных методов сортировки представляет собой довольно сложную математическуюзадачу.
Те оценки, которые приведены ниже, заимствованы из литературных источников. Рассмотримнесколько разных алгоритмов сортировки – от самых простых и самых медленных до одного из наиболееэффективных.Сортировка методом пузырькаИдея метода состоит в сравнении двух соседних элементов, в результате чегоменьшее число (более легкий "пузырек") перемещается на одну позицию влево. Обычнопросмотр организуют с конца, и после первого прохода самое маленькое числоперемещается на первое место. Затем все повторяется от конца массива до второгоэлемента и т.д. Известен и другой вариант пузырьковой сортировки, в котором такжесравнивают два соседних элемента, и если хотя бы одна из смежных пар былапереставлена, то просмотр начинают с самого начала.Функция bubble, реализующая первый алгоритм пузырьковой сортировки приведенаниже: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; }42}Более известный алгоритм пузырьковой сортировки реализован в функции bubble1.В ней использована флажковая переменная q, которая принимает ненулевое значение вслучае перестановки какой-либо смежной пары:void bubble1(int *x, int n){ register int i,j;int tmp,q;m: q=0;for(i=1;i<n-1;i++)if(x[i]>x[i+1]){ tmp=x[i]; x[i]=x[i+1]; x[i+1]=tmp; q=1;}if(q) goto m;}Пузырьковая сортировка неплохо работает, когда в исходных данных многиеэлементы уже упорядочены.
Если исходный массив уже отсортирован, то работа функцииограничивается первым проходом. В худшем случае (массив упорядочен по убыванию)количество сравнений составляет n*(n-1)/2, а количество перестановок достигает 3*n*(n1)/2. Среднее количество перестановок равно 3*n*(n-1)/4.Сортировка методом отбораИдея метода: находится элемент с наименьшим значением и меняется местами спервым элементом. Среди оставшихся элементов ищется наименьший, который меняетсясо вторым и т.д. Функция 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; }}}Сортировка методом отбора является n-квадратичным алгоритмом.
Внешний цикл выполняется n-1раз, а внутренний n/2. В результате производится n*(n-1)/2 сравнений, что замедляет работы алгоритма прибольшом количестве элементов в массиве. В наилучшем случае, если список уже упорядочен требуетсясравнить только n-1 элемент и каждое сравнение требует трех промежуточных шагов. Наихудший случайаппроксимирует количество перестановок. Количество перестановок для среднего случае вычисляется поформуле n(log n + y), y – константа Эйлера (0.577216).Оценка трудоемкости метода отбора:• количество сравнений – n*(n-1)/2;• количество перестановок:o в лучшем случае – 3*(n-1)o в худшем случае –n2/4+3*(n-1)o в среднем – n*(log n +0.577216)Хотя количество сравнений для пузырьковой сортировки и сортировки методом отбора одинаковы,однако, для сортировки отбором показатель количества перестановок в среднем случае намного лучше.
Темне менее, существуют еще более совершенные методы сортировки.Сортировка методом вставкиИдея метода: последовательное пополнение ранее упорядоченных элементов. Напервом шаге сортируются два первые элемента. Затем на свое место среди нихвставляется третий элемент. К трем упорядоченным добавляется четвертый, которыйзанимает свое место в четверке и т.д. Примерно так игроки упорядочивают свои картыпри сдаче их по одной.
Функция insert, реализующая описанную процедуру, приведенаниже:void insert(int *x, int n)43{ 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;}}В отличии от метода пузырьковой сортировки и сортировки методом отбораколичество сравнений, имеющих место в процессе сортировки методом вставки, зависитот исходной упорядоченности списка. Если массив уже отсортирован, то все равнопотребуется 2*(n-1) сравнение. Если массив упорядочен по убыванию, то число сравненийвозрастает до n*(n+1)/2. По этой причине в наихудших случаях алгоритм вставки так жеплох, как и пузырьковый метод или метод отбора. В среднем случае он лишь немногимлучше предыдущих методов. Однако, поведение алгоритма сортировки методом вставкиестественно.
Это означает, что если массив уже отсортирован в нужном порядке, алгоритмпроводит наименьшее количество вычислений, а если массив отсортирован в обратномпорядке – его работа наиболее интенсивна.Сортировка методом ШеллаВ 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;}}}Быстрая сортировкаИзвестный математик C.A.R. Hoare в 1962 году опубликовал алгоритм быстройсортировки, за которым закрепилось название quicksort.
Основная идея быстройсортировки напоминает метод поиска делением пополам. Сначала выбирается граничныйэлемент в сортируемом массиве, его называют компарандом. Все, что больше этогоэлемента переносится в правую часть массива, а все, что меньше – в левую. После первогошага средний элемент оказывается на своем месте.
Затем аналогичная процедураповторяется для каждой половины массива. На каждом последующем шаге размеробрабатываемого фрагмента массива уменьшается вдвое. Количество операций, котороетребуется для реализации этой процедуры, оценивается константой n*log2n. Это ещебыстрее, чем сортировка Шелла. В отличие от предыдущих функций быстрая сортировка44оформлена из двух функций – quick, которая допускает принятое в других функцияхобращение, и рекурсивной процедуры qs:void quick(int *x, int n){ 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. Эти показатели существенноменьше, чем у рассмотренных выше методов сортировки. Следует иметь в виду, еслизначение-компаранд для каждого из разделов является максимальным, то на практикеметод быстрой сортировки вырождается в метод «медленной» сортировки с временемвыполнения, пропорциональным квадрату количества элементов.45УказателиУказатели - это переменные, которые хранят адреса объектов. В неявном видеуказатели присутствовали и в других языках программирования, но в Си онииспользуются гораздо чаще, а работа с указателями организована максимально просто.При описании указателя надо задать тип объектов, адреса которых будутсодержаться в нем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
