1 Программирование на языке Паскаль Тема 4. Сортировка массивов

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] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат: