БЫСТРЫЕ СОРТИРОВКИ Студент 2 курса МГИМО-Ташкент Ташматов Али - Быстрая обменная сортировка (сортировка Хоара).
- Быстрая сортировка вставкой (сортировка Шелла).
- Быстрые сортировки выбором.
- Сравнительный анализ методов сортировки.
4.10. Быстрая обменная сортировка (сортировка Хоара) - Считается самой эффективной из известных внутренних сортировок.
- Получила название – Quicksort
Быстрая обменная сортировка (сортировка Хоара) Идея алгоритма: - Из исходного массива выбирается некоторый элемент, который принимается в качестве разделителя или опорного элемента.
- Все ключи, меньшие разделителя, располагаются до него, а все большие – после него.
- Перестановка элементов выполняется путём обмена местами ключей, которые необходимо переместить в другую часть массива.
- При этом обмениваются ключи, расположенные на большом расстоянии друг от друга и этим достигается наивысший эффект упорядочивания.
Hoor(left, right:integer) - в Pascal или функция void hoor(int left,right) – в C++ Алгоритм является рекурсивным. Обозначения переменных: right – правая граница рассматриваемой части массива A; left – левая граница рассматриваемой части массива A; x – разделитель. При первом вызове процедуры полагается: right = n; в C++ -> right = n-1; left = 1; в C++ -> left = 0; Сортировка Хоара (Pascal) procedure Hoor(left, right:integer); var i,j,x:integer; begin i:=left; j:=right; x:=a[(left+right) div 2]; repeat while a[i]do i:=i+1; {поиск с левой стороны элемента большего, чем разделитель} while xdo j:=j-1; {поиск с правой стороны элемента меньшего, чем разделитель} if i<=j then begin меняем местами a[i] и a[j]; i:=i+1;j:=j-1 end; until i>j; if leftthen Hoor(left,j); {применить процедуру сортировки для левой части массива} if ithen Hoor(i,right); {применить процедуру сортировки для правой части массива} end; Сортировка Хоара (C/C++) void hoor(int left, int right) { int i=left; int j=right; int x=a[(left+right)/2]; do { while (a[i]<=x) i++; //поиск с левой стороны элемента большего, чем разделитель while (x //поиск с правой стороны элемента меньшего, чем разделитель if (i<=j) { меняем местами a[i] и a[j]; i++;j--; } } while (i<=j); if (left //применить процедуру сортировки для левой части массива if (i //применить процедуру сортировки для правой части массива } - Среднее время выполнения алгоритма:
T(n) = O(n × log n) - Если массив почти упорядочен, время работы алгоритма может возрасти до квадратичного!
- Чтобы избежать этого, выбор разделителя производится методом медианы случайной выборки.
- Доказано, что наилучший обмен ключами достигается, когда разделитель разбивает массив по значениям «меньше разделителя» и «больше разделителя» примерно на равные части, т.е. разделитель близок к медиане.
- Из массива произвольно выбирается группа элементов (обычно до ста элементов), которые сортируются любым простым методом.
- Из середины отсортированной последовательности выбирается элемент, который далее используется в качестве разделителя.
Быстрая обменная сортировка (сортировка Хоара) - Пример 4.11. Быстрая сортировка вставкой – сортировка Шелла - Сортировка Шелла является видом сортировки вставкой с изменяющимся расстоянием между сравниваемыми ключами.
- Наибольшее в начале, оно сокращается до 1 по мере упорядочения ключей.
- Этим достигается скорейшее продвижение ключей к своим истинным местам.
- Временная сложность алгоритма:
T(n) = O(n×log n) https://www.youtube.com/watch?v=CmPA7zE8mx0 Идея алгоритма: Идея алгоритма: - Исходный массив разбивается на несколько подмассивов.
- В качестве подмассива выбираются элементы, удалённые на d шагов, т.е. значения индексов соседних элементов подмассива отличается на величину, равную d.
- Сортируем массивы и уменьшаем d, процесс продолжается до тех пор, пока d не станет равно 1.
- На эффективность сортировки Шелла существенным образом влияет выбор закона изменения расстояния d.
Основное требование: - расстояния di, di-1, …, d1 не должны быть кратны одно другому.
- Используют один из двух вариантов расчёта элементов последовательности di, di-1, …, d1.
Вариант №1 di = 2di-1 + 1, t – количество используемых расстояний, t = [log2 n] – 1, где [b] – целая часть числа b, d1 = 1; Вариант №2 di = 3di-1 + 1, t = [log3 n] – 1, d1 = 1. Быстрая сортировка вставкой – сортировка Шелла - пример Обозначения: A – исходный массив; t – количество расстояний; d – массив расстояний; x – вставляемый на текущем шаге элемент. Сортировка Шелла (Pascal) t:=trunc(log2(n))-1; {количество расстояний} d[1]:=1; for i:=2 to t do d[i]:=2*d[i-1]+1; {формирование последовательности di по первому варианту} for m:=t downto 1 do {выбор текущего расстояния} begin k:=d[m]; for i:=k+1 to n do begin x:=a[i]; {запомнить вставляемый ключ} j:=i-k; while (j>0) and (xdo {сравнение элементов, находящихся на расстоянии d с вставляемым ключом} begin a[j+k]:=a[j]; j:=j-k end; a[j+k]:=x; {вставка ключа} end end; Сортировка Шелла (C++) t=(int)log((double)n)-1; //количество расстояний d[0]=1; for (i=1; i //формирование последовательности di по первому варианту for (m=t-1;m>=0;m--) { //выбор текущего расстояния k=d[m]; for (i=k;i x=a[i]; //запомнить вставляемый ключ j=i-k; while ((j>=0) && (x сравнение элементов, находящихся на расстоянии d с вставляемым ключом a[j+k]=a[j]; j=j-k; } a[j+k]=x; //вставка ключа } } Быстрые сортировки выбором На практике используется несколько сортировок выбором. Наиболее известные: - «Турнир с выбыванием»;
- Пирамидальная сортировка.
4.12. Сортировка «Турнир с выбыванием» Идея алгоритма: - Элементы массива разбиваются на пары.
- Из каждой пары выбирается победитель (меньший из элементов).
- Из победителей пар образуется новый массив, и процесс отбора победителей повторяется до тех пор, пока не будет найден победитель турнира.
- Этот победитель исключается из исходного массива и заносится в выходной массив.
- В изменённом исходном массиве находится новый победитель.
- Процесс повторяется до тех пор, пока в исходном массиве будут оставаться элементы.
Алгоритм «Турнир с выбыванием» - Сравниваем пары соседних ключей и запоминаем значение меньшего ключа из каждой пары.
- Выполняем пункт 1 по отношению к значениям, полученным на предыдущем шаге, до тех пор, пока не определим наименьший ключ – «победитель турнира» и не построим дерево турнира:
- Вносим значение, найденное в п.2 в массив упорядоченных ключей (дополнительный массив).
- Проходим от корня к листу дерева, следуя по пути, отмеченному значениями «победителя турнира» (на схеме отмечены *), и заменяем значение в листе на max – наибольшее допустимое целое число (например, 100).
- Проходим от листа к корню, по пути обновляя значения в узлах дерева, и определяем нового победителя турнира.
Оценка временной сложности алгоритма: - Для выполнения пунктов 1-2 потребуется сделать n-1 сравнений.
- Для коррекции дерева потребуется не более log n сравнений, т.е. длина пути от корня к листу не превышает величину log n.
- Дерево придётся корректировать n-1 раз, поэтому временная сложность алгоритма равна:
T(n)=k1×(n-1)+k2×(log n)×(n-1)=O(n×log n), k1, k2 – константы, зависящие от реализации алгоритма на компьютере. Достоинства: Достоинства: - Быстрота. Оценки худшего и среднего времени выполнения алгоритма совпадают.
Недостатки: - Дополнительный расход памяти на хранение дерева турнира и результатов сортировки.
Этот недостаток устранён в пирамидальной сортировке. 4.13. Пирамидальная сортировка Выполняется на базе дерева. Алгоритм состоит из 2-х этапов: - Построение пирамиды на месте исходного массива.
- Сортировка пирамиды.
- На данном этапе концевые элементы пирамиды меняются значениями, и она укорачивается справа на один элемент, который является вершиной пирамиды.
- Полученный укороченный массив уже не может быть пирамидой, поэтому снова делается пирамидой с помощью специальной процедуры.
- Повторяя этот этап n раз, получаем отсортированный массив A, в котором: a[1]<=a[2]<= … <=a[n]
Бинарное дерево можно представить в виде одномерного массива, в котором: a[1] – корень дерева; a[2i] – левый сын a[i]; a[2i+1] – правый сын a[i]. - Данное дерево будет являться пирамидой, если для любого i-го элемента, имеющего потомков, выполняются неравенства:
a[i]>=a[2i] a[i]>=a[2i+1] am, … , an (m=n div 2 + 1) уже образует пирамиду (у этих элементов нет потомков – это нижний слой соответствующего дерева и для них никакой упорядоченности не требуется). Далее пирамида расширяется влево, при этом каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Если у нас уже готова пирамида a[k+1], … , a[n], то можно её расширить до пирамиды a[k], … , a[n], используя для a[k] процедуру добавления элемента. Процедура добавления элемента в готовую пирамиду (Pascal) procedure Shift(left,right:integer); begin i:=left; j:=2*left; x:=a[left]; {Новый элемент x помещаем а вершину дерева, left – номер элемента, включаемого в пирамиду, right – номер последнего элемента массива} if (jand (a[j+1]>a[j]) then j:=j+1; {Условие jконтролирует выход за пределы массива, определяется наибольший потомок} while (j<=right) and (xdo begin x:=a[i]; a[i]:=a[j]; a[j]:=x; {Обмен элементов массива} i:=j; j:=2*j; if (jand (a[j+1]>a[j]) then j:=j+1 {Определение нового узла} end; end; Функция добавления элемента в готовую пирамиду (С++) void shift(int left,right) { int i,j,x; i=left; j=2*left; x=a[left]; // Новый элемент x помещаем в вершину дерева, // left – номер элемента, включаемого в пирамиду, // right – номер последнего элемента массива if ((ja[j])) j++; //Условие jконтролирует выход за пределы // массива, определяется наибольший потомок while ((j<=right) && (x x=a[i]; a[i]=a[j]; a[j]=x; //Обмен элементов массива i=j; j=2*j; if ((ja[j])) j++; //Определение нового узла } a[i]=x; } Pascal: C/C++: left:=n div 2; left=n/2; while left>1 do while (left>1) begin { left:=left-1; left--; Shift(left,n) shift(left,n); end; } - После превращения массива в пирамиду получается частично упорядоченная последовательность элементов.
- Для достижения полной упорядоченности надо проделать n сдвигающих шагов, причём после каждого шага на вершину ( в корень) дерева помещается очередной наибольший элемент.
- В пирамиде первый элемент не меньше всех остальных.
- Для хранения «всплывающих» в корень элементов обменяем значениями первый и последний элементы пирамиды и укоротим пирамиду на один элемент справа.
- После этого укороченный массив может не быть пирамидой.
- Применим к нему процесс «просеивания» для элемента ai.
- Преобразованная последовательность станет пирамидой.
- Повторяя этот процесс n-1 раз отсортируем массив A по возрастанию.
Pascal: right:=n; while right>1 do begin x:=a[1]; a[1]:=a[right]; a[right]:=x; right:=right-1; Shift(1,right); end; C/C++: right=n; while (right>1) { x=a[1]; a[1]=a[right]; a[right]=x; right--; shift(1,right); } Реализация пирамидальной сортировки (Pascal) left:=n div 2; right:=n; {определяем место элемента, у которого нет потомков и номер последнего просматриваемого элемента} while left>1 do {пока не достигнем вершины} begin left:=left-1; Shift(left,right) end; while right>1 do begin x:=a[1]; a[1]:=a[right]; a[right]:=x; right:=right-1; Shift(1,right) end; Реализация пирамидальной сортировки (C/C++) left=n/2; right=n; //определяем место элемента, у которого нет потомков и номер последнего просматриваемого элемента while (left>1)//пока не достигнем вершины { left--; shift(left,right); } while (right>1) { x=a[1]; a[1]=a[right]; a[right]=x; right--; shift(1,right); } - Данное дерево не является пирамидой, поэтому его надо изменить.
- Представим пирамиду, состоящую только из нижнего уровня, т.е. из 8 элементов
a[8], … , a[15] - Далее будем добавлять в массив по одному элементу, вставляя его в нужное место.
Шаг 1 Шаг 1 Добавляем элемент a[7]=40. У него два потомка a[14]=25 и a[15]=71. Т.к. a[7]< max(a[14],a[15]), то меняем местами a[7] и a[15]. Шаг 2 Добавляем элемент a[6]=19 и меняем его местами с a[12]=41. Добавляем элемент a[5]=4 и меняем его местами с a[10]=82. Добавляем элемент a[4]=34 и меняем его местами с a[8]=75. В итоге максимальный элемент наверху. Построение пирамиды закончилось. Далее этап сортировки. Не на своём месте a[1], его надо «просеять». Для этого меняем местами a[1] и a[2], a[2] и a[4]. - Сравнение быстродействия различных алгоритмов сортировки можно выполнить по ряду показателей:
- среднему времени выполнения алгоритма;
- максимальному времени выполнения алгоритма;
- минимальному времени выполнения алгоритма;
- Достаточно часто анализ эффективности алгоритмов производится подсчётом количества выполненных операций сравнения и пересылки.
Формулы, определяющие количество операций, выполняемых с ключами при использовании простых методов сортировки Количество операций сравнения, выполняемых при использовании различных методов сортировки - Для простых сортировок при увеличении размера массива в 10 раз количество операций возрастает примерно в 100 раз.
- Для быстрых сортировок при увеличении размера массива в 10 раз количество операций возрастает примерно в 15-19 раз.
Временная сложность: - простых сортировок - O(n2);
- быстрых сортировок - O(n×log n).
|
Скачать 2.47 Mb.