15.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 SAOD, dep.OSU, TPU16 Сортировка включением

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

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

19 SAOD, dep.OSU, TPU19 Сортировка Шелла Для достаточно больших массивов рекомендуемой считается такая последовательность, что 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)

20 SAOD, dep.OSU, TPU20 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;

21 SAOD, dep.OSU, TPU21 Сэджвик (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 перемещений. Сортировка Шелла

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

23 SAOD, dep.OSU, TPU23 Простое извлечение 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; Сортировка извлечением (выбором)

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

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

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

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

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

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

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

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

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

33 SAOD, dep.OSU, TPU33 Пирамида (двоичное дерево) определяется как последовательность 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)

34 SAOD, dep.OSU, TPU34 Алгоритм Флойда: Построение пирамиды на «том же месте»: пусть 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)

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

36 SAOD, dep.OSU, TPU36 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)

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

38 SAOD, dep.OSU, TPU38 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)

39 SAOD, dep.OSU, TPU39 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)

40 SAOD, dep.OSU, TPU40 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)

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