Алгоритмы сортировки

2 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» (Quick Sort) сортировка «кучей» (Heap Sort) сортировка слиянием пирамидальная сортировка сложность O(N 2 ) сложность O(N·logN) время N O(N 2 ) O(N·logN)

3 Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает») начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место ый проход 2-ой проход 3-ий проход Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

4 Программа 1-ый проход: 5 2 … … N-1 N сравниваются пары A[N-1] и A[N], A[N-2] и A[N-1] … A[1] и A[2] A[j] и A[j+1] 2-ой проход A[1] уже на своем месте! ! for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 2 for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 1 i -ый проход for j:=N-1 downto i do... for j:=N-1 downto i do... i 1 5 … … N-1 N

5 Программа program qq; const N = 10; var A: array[1..N] of integer; i, j, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; Почему цикл по i до N-1 ? ? i элементы выше A[i] уже поставлены

6 Метод пузырька с флажком Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход. repeat flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } repeat flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } flag := False; flag := True; not flag; var flag: boolean; Как улучшить? ?

7 Метод пузырька с флажком i := 0; repeat i := i + 1; flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; repeat i := i + 1; flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; i i := i + 1;

8 Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2] ), и т.д

9 Метод выбора for i := 1 to N-1 do begin nMin = i ; for j:= i+1 to N do if A[j] < A[nMin] then nMin:=j; if nMin <> i then begin c:=A[i]; A[i]:=A[nMin]; A[nMin]:=c; end; N-1 N нужно N-1 проходов поиск минимального от A[i] до A[N] если нужно, переставляем Можно ли убрать if ? ? i+1 i

10 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре. Пример: Исходный массив: Результат: «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат:

11 «Быстрая сортировка» (Quick Sort) Идея – более эффективно переставлять элементы, расположенные дальше друг от друга. Сколько перестановок нужно, если массив отсортирован по убыванию, а надо – по возрастанию? ? N div 2 2 шаг: переставить элементы так: при сортировке элементы не покидают « свою область»! 1 шаг: выбрать некоторый элемент массива X A[i] <= XA[i] >= X 3 шаг: так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer)

12 «Быстрая сортировка» (Quick Sort) Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…). Разделение: 1)выбрать средний элемент массива ( X=67 ) 2)установить L:=1, R:=N 3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа) 4)уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева) 5)если L<=R, поменять местами A[L] и A[R] и перейти к п Как лучше выбрать X? ?

13 «Быстрая сортировка» (Quick Sort) LR LR LR RL L > R : разделение закончено !

14 «Быстрая сортировка» (Quick Sort) procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; QSort(first, R); QSort(L, last); end; end. procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; QSort(first, R); QSort(L, last); end; end. ограничение рекурсии while L <= R do begin while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L + 1; R:= R - 1; end; разделение обмен двигаемся дальше сортируем две части

15 «Быстрая сортировка» (Quick Sort) program qq; const N = 10; var A: array[1..N] of integer; begin { заполнить массив } { вывести исходный массив на экран } Qsort ( 1, N ); { сортировка } { вывести результат } end. program qq; const N = 10; var A: array[1..N] of integer; begin { заполнить массив } { вывести исходный массив на экран } Qsort ( 1, N ); { сортировка } { вывести результат } end. procedure QSort ( first, last: integer);... Сложность (в среднем) ! !

NQuickSort«пузырек» Количество перестановок (случайные данные) От чего зависит скорость? ? Как хуже всего выбирать X? ?

17 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и отсортировать его по убыванию с помощью алгоритма быстрой сортировки. «5»: Заполнить массив из 500 элементов случайными числами в интервале [0..100]. Отсортировать его по возрастанию двумя способами – методом «пузырька» и методом «быстрой сортировки». Вывести на экран число перестановок элементов массива в том и в другом случае. Массив выводить на экран не нужно.