09.12.2013SAOD, dep.OSU, TPU1 Методы сортировки Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка. - презентация

1 SAOD, dep.OSU, TPU1 Методы сортировки Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >,

2 SAOD, dep.OSU, TPU2 Методы сортировки Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (ключ сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", " =" и " ", " =" и "">

3 SAOD, dep.OSU, TPU3 Методы сортировки внутренняя сортировка, в которой предполагается, что данные находятся в оперативной памяти, и важно оптимизировать число действий программы (для методов, основанных на сравнении, число сравнений, обменов элементов и пр.) внешняя, в которой данные хранятся на внешнем устройстве с медленным доступом (магнитные лента, барабан, диск) и прежде всего надо снизить число обращений к этому устройству.

4 SAOD, dep.OSU, TPU4 Методы внутренней сортировки Методы сортировки Подсч етом Включен ием (вставок) Извлечен ием (выбором) Обмен ами Слиян ием Распр еделе нием Простым включен ием Шелл а Прост ым извле чени ем Пира мида льна я Пузы рько вая Быстрая (Хоара)

5 SAOD, dep.OSU, TPU5 Сортировка подсчетом В сортировке подсчетом (counting sort) предполагается, что все n входных элементов целые числа, принадлежащие интервалу от 0 до k, где k - некоторая целая константа.

6 SAOD, dep.OSU, TPU6 Сортировка подсчетом Основная идея сортировки подсчетом заключается в том, чтобы для каждого рассматриваемого элемента х определить количество элементов, которые меньше х. С помощью этой информации элемент х можно разместить на той позиции выходного массива, где он должен находиться.

7 SAOD, dep.OSU, TPU7 Сортировка подсчетом Исходный массив: A[1..n] Результат: B[1..n] Вспомогательный массив С[0..k]

8 SAOD, dep.OSU, TPU8 Сортировка подсчетом

9 SAOD, dep.OSU, TPU9 Сортировка подсчетом

10 SAOD, dep.OSU, TPU10 Сортировка подсчетом Временная сложность- O(n+k)

11 SAOD, dep.OSU, TPU11 Сортировка включением (вставками) Массив делится на 2 части: Отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и включается в отсортированную

12 SAOD, dep.OSU, TPU12 Сортировка включением Простое включение Отсортировано начало массива A 1, A 2, ….,A i-1 Остаток массива A i,…A n – неотсортирован. На очередном шаге Ai включается в отсортированную часть на соответствующее место

13 SAOD, dep.OSU, TPU13 Сортировка включением

14 SAOD, dep.OSU, TPU14 Сортировка включением

15 SAOD, dep.OSU, TPU15 Сортировка включением Алгоритм имеет сложность O(n 2 ), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет O(n).

16 2. Сортировка включениемСортировка public static void simpleSort(int[] data) { int i, j; for (i = 1; i < data.length; i++) { int c = data[i]; for (j = i-1; j >= 0 && data[j] > c; j--) { data[j+1] = data[j]; } data[j+1] = c; }

17 SAOD, dep.OSU, TPU17 Сортировка включением Бинарные вставки ( число сравнений NlgN)

18 SAOD, dep.OSU, TPU18 Сортировка Шелла (Donald Shell, 1959г.)

19 SAOD, dep.OSU, TPU19 Сортировка Шелла (Donald Shell, 1959г.) Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и тд, где h - положительная константа. Таким образом формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно. Процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.

20 SAOD, dep.OSU, TPU20 Сортировка Шелла Для достаточно больших массивов рекомендуемой считается такая последовательность, что h i+1 =3h i +1, а h 1 =1. Начинается процесс с h m-2, h m-2 первый такой член последовательности, что h m-2 [n/9]. 1, 4, 13, 40, 121…( h i+1 =3h i +1) 1, 3, 7, 15, 31 ( h i+1 =2h i +1)

21 SAOD, dep.OSU, TPU21 h 1; while h < N div 9 do h h*3 + 1; repeat // цикл по сериям for k 1... h do {сортировка k-ой серии} i h + k; while i = 1) and (A[j]>x) do //сдвиг A[j + h] A[j]; j j -h); A[j + h] x; ii + h); h := h div 3;{переход к нов.серии} while h>0;

22 SAOD, dep.OSU, TPU22 Сэджвик (1986г) (h 0,h 1,h 2,…)=(1,5,19,41,109,209..) Конец последовательности – h t-1 если 3h t n среднее количество операций: O(n 7/6 ), в худшем случае - порядка O(n 4/3 ). в среднем 1,66n 1,25 перемещений. Сортировка Шелла

23 4. Сортировка Шелла step= step= step= step=1

24 4. Сортировка ШеллаСортировка Шелла public static void ShellSort(int[] data) { int n = data.length; // Длина массива int step = n; // Шаг поисков и вставки int i, j; do { // Вычисляем новый шаг step = step / 3 + 1; // Производим сортировку простыми вставками с заданным шагом for (i = step; i < n; i++) { int c = data[i]; for (j = i-step; j >= 0 && data[j] > c; j -= step) { data[j+step] = data[j]; } data[j+step] = c; } } while (step != 1); } Количество перестановок элементов (по результатам экспериментов со случайным массивом) n = 25n = 1000n = Сортировка Шелла Сортировка простыми вставками млрд.

25 SAOD, dep.OSU, TPU25 Вариант 1 массив делится на уже отсортированную часть A i+1, A i+2 …А n и неотсортированную A 1, A 2, ….,A i 1.На каждом шаге извлекается мах из неотсортированной части 2.Найденный мах ставится в начало отсортированной части Сортировка извлечением (выбором)

26 SAOD, dep.OSU, TPU26 Простое извлечение for i N downto 2 do MaxIndex 1; for j 2 to i do if A[j]>A[MaxIndex] then MaxIndex j; Tmp A[i]; A[i] A[MaxIndex]; A[MaxIndex] Tmp; Сортировка извлечением (выбором)

27 SAOD, dep.OSU, TPU27 Сортировка извлечением (выбором)

28 SAOD, dep.OSU, TPU28 Вариант 2 последовательность создается, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная с первого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов A[i]... A[n] и меняем его местами с A[i]. Сортировка извлечением (выбором)

29 SAOD, dep.OSU, TPU29 Сортировка извлечением (выбором) ниже.

30 SAOD, dep.OSU, TPU30 С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций: n + (n-1) + (n-2) + (n-3) = 1/2 * ( n 2 -n ) = O(n 2 ). Сортировка извлечением (выбором) ниже.

31 SAOD, dep.OSU, TPU31 Усовершенствование простого выбора: Лемма. В любом алгоритме нахождения максимума среди n элементов, основанном на сравнении пар элементов, необходимо выполнить, по крайней мере, n 1 сравнений. Сортировка извлечением(выбором) ниже.

32 SAOD, dep.OSU, TPU32 Сортировка извлечением (выбором) ниже.

33 SAOD, dep.OSU, TPU33 В общем случае, если n точный квадрат, можно разделить массив на n групп по n элементов Любой выбор, кроме первого, требует не более чем n -2 сравнений внутри группы ранее выбранного элемента плюс n -1 сравнений среди "лидеров групп Этот метод получил название квадратичный выбор общее время его работы составляет порядка O(n n ) что существенно лучше, чем O(n 2 ) Сортировка извлечением(выбором) ниже.

34 SAOD, dep.OSU, TPU34 В алгоритме выбора проделав n-1 сравнение, мы можем построить дерево выбора и идентифицировать его корень как мин элемент Второй этап сортировки – спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева Элемент продвинувшийся в корень опять будет мин После n шагов дерево становится пустым и сортировка заканчивается Heapsort (Williams,Floyd)

35 SAOD, dep.OSU, TPU35 tree1 На каждом из n шагов выбора требуется только log n сравнений. Поэтому на весь процесс понадобится порядка n*log(n), т.е. T(n) = O(n*log n ) элементарных операций и n шагов на построение дерева Heapsort (Williams,Floyd)

36 SAOD, dep.OSU, TPU36 Пирамида (двоичное дерево) определяется как последовательность H L, H L+1, … H R такая, что H i H 2i & H i H 2i+1 для i=L …R/2 H1 = min(H 1, H 2,…H N ) tree2 Heapsort (Williams,Floyd)

37 SAOD, dep.OSU, TPU37 Алгоритм Флойда: Построение пирамиды на «том же месте»: пусть H 1, H 2,…H N есть сортируемый массив, причем H M,…H N, где M= (N div 2) +1 образует нижний слой пирамиды, поскольку нет индексов i, j таких что j=2i или j=2i +1, т.е. для этого слоя упорядоченности не требуется Heapsort (Williams,Floyd)

38 SAOD, dep.OSU, TPU38 Алгоритм Флойда: Пирамида расширяется влево - каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент, пока элементы стоящие слева от H M не будут образовывать пирамиду (tree2) (table1)tree2table1 Такая процедура называется – Sift Heapsort (Williams,Floyd)

39 SAOD, dep.OSU, TPU39 Sift(L, R: index); // i, j: index; x: item; х – элемент вставляемый в пирамиду // i, j - пара индексов, фиксирующих элементы, меняющиеся на каждом шаге местами. i L; j 2*L; X a[L]; if (j < R) & (a[j+1] < a[j]) then j j+1 while (j < = R) & (a[j] < X) do a[i] a[j]; a[j] X; i j; j 2*j; if (j < R) & (a[j+1] < a[j] then j j+1 // end Sift; Heapsort (Williams,Floyd)

40 SAOD, dep.OSU, TPU40 Процесс формирования пирамиды из n элементов h 1... h n. на том же самом месте описывается так: L (n div 2)+ 1; while L > 1 do L L - 1; sift(L, n) table1 Heapsort (Williams,Floyd)

41 SAOD, dep.OSU, TPU41 n сдвигающих шагов выталкивания наименьших элементов на вершину дерева с последующим смещением в конец массива: R n; while R>1 do x a[1]; a[1] a[R]; a[R] x; R R-1; sift(1,R ) table2 Heapsort (Williams,Floyd)

42 Пирамидальная сортировка (HeapSort) И так далее…

43 Пирамидальная сортировка (продолжение) И так далее…

44 Алгоритм пирамидальной сортировки public static void heapSort(int[] data) { int n = data.length; // Длина массива buildPyramid: // Построение пирамиды for (int i = 1; i < n; i++) { // Inv: Элементы data[0:i-1] уже образуют пирамиду; int c = data[i]; // "Протаскиваемое" значение int p = i, q; // Индексы для "протаскивания" вверх к вершине do { q = p; if ((p = (q-1) >> 1) >= 0 && data[p] < c) data[q] = data[p]; else { data[q] = c; continue buildPyramid; } } while (true); } meltPyramid: // Постепенное разрушение пирамиды for (int i = n-1; i > 0; i--) { int c = data[i]; data[i] = data[0]; int q, p = 0; // Индексы для протаскивания do { q = p; p = (q = i) { // Вышли за границу пирамиды data[q] = c; continue meltPyramid; } if (p data[p]) p++; if (data[p] > c) data[q] = data[p]; else { data[q] = c; continue meltPyramid; } } while (true); } > 1) >= 0 && data[p] < c) data[q] = data[p]; else { data[q] = c; continue buildPyramid; } } while (true); } meltPyramid: // Постепенное разрушение пирамиды for (int i = n-1; i > 0; i--) { int c = data[i]; data[i] = data[0]; int q, p = 0; // Индексы для протаскивания do { q = p; p = (q = i) { // Вышли за границу пирамиды data[q] = c; continue meltPyramid; } if (p data[p]) p++; if (data[p] > c) data[q] = data[p]; else { data[q] = c; continue meltPyramid; } } while (true); }">

45 SAOD, dep.OSU, TPU45 Procedure HeapSort; var L, R: index; x: item; Procedure sift(L, R: index); var i, j: index; x: item; begin i := L; j := 2*L; X := a[L]; if (j < R) & (a[j+1] < a[j] then j := j+1 while (j < = R) & (a[j] < X) do begin a[i]:=a[j]; a[j]:= X; i:=j; j:=2*j; if (j < R) & (a[j+1] < a[j] then j := j+1 end; end sift; Heapsort (Williams,Floyd)

46 SAOD, dep.OSU, TPU46 begin L:=(n div 2)+ 1;R := n; while L > 1 do begin L :== L - 1; sift(L, r) end; while R>1 do begin x:=a[1]; a[1] := a[R]; a[R] := x; R := R-1; sift(1,R ) end; end HeapSort; Heapsort (Williams,Floyd)

47 SAOD, dep.OSU, TPU47 В самом плохом из возможных случаев Heapsort потребует n*log n шагов. т.е. T(n) = O (n*log n) Heapsort «любит» начальные последовательности, в которых элементы более или менее отсортированы, то фаза порождения пирамиды потребует мало перемещений. Среднее число перемещений приблизительно равно n/2*log(n), причем отклонения от этого значения незначительны. Heapsort (Williams,Floyd)