Сортировка с помощью прямого выбора (линейная)

1. В массиве, содержащем n элементов, выбирается наименьший элемент.

2. Этот элемент меняется местами с первым элементом a₁.

3. Процесс повторяется с оставшимися n-1, n-2 и т.д. элементами, пока не останется один элемент.

• СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ

Procedure StraigthSelection; Var I, j, k:Integer; x:Integer; begin for i:=1 to n-1 do begin k:=i; x:=a[i]; for j:=i+1 to n do if a[j]<x then begin k:=j; x:=a[k]; end; a[k]:=a[i]; a[i]:=x; end; end;

• См. также 681.3 В52 Вирт Н. Алгоритмы и структуры данных. Сортировка с помощью дерева (пирамидальная сортировка, HeapSort).

Сортировка с помощью прямого обмена (пузырьковая)

Алгоритм основан на сравнении и, при необходимости, обмене значений в паре соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.

При проходах по массиву наибольший (наименьший) элемент смещается к правому краю массива. После этого область возможного перемещения уменьшается на 1 и аналогичным образом рассматриваются оставшиеся n-1, n-2, …, 2 элементов.

• СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ

PROCEDURE BubbleSort; VAR i, j:Integer; x:Integer; BEGIN for i:=N Downto 2 do for j:=1 to i-1 do if a[j] > a[j+1] then begin x := a[j]; a[j]:=a[j+1]; a[j+1]:=x end END {BubbleSort};

Быстрая сортировка (ч. Хоара, сортировка с помощью разделения)

Алгоритм быстрой сортировки (Quicksort) считается одним из лучших методов сортировки массивов.

• ОПИСАНИЕ РЕКУРСИВНОГО АЛГОРИТМА:

1. выбирается произвольный элемент (х);

2. просматривается левая от х часть массива, пока не обнаружим элемент a_i>х;

3. просматривается правая от х часть массива, пока не обнаружим элемент a_j<х;

4. меняются местами a_i и a_j;

5. повторяются шаги 2-4, пока оба просмотра не встретятся в середине массива (i<j).

• В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) х, и правую - с ключами больше (или равными) х. Применим описанный выше процесс к получившимся двум (левой и правой) частям массива, затем - к частям этих частей, и так до тех пор, пока каждая из частей не будет состоять из одного элемента.

PROCEDURE Quicksort; PROCEDURE sort(L,R:index); VAR i,j: integer; w,x: integer; BEGIN i:= L; j:= R; x:=a[(L+R) div 2]; REPEAT WHILE a[i]<x DO i:=i+1; WHILE x<a[j] DO j:=j-1; IF i<=j THEN begin w:=a[i]; a[i]:=a[j]; a[j]:=w; i:=i+1; j:=j-1 end UNTIL i>j; IF L<j THEN sort(L,j); IF i<R THEN sort(i,R) END {sort}; BEGIN sort(1,n) END; {Quicksort}

• ТЕМА. ПРОЦЕДУРЫ И ФУНКЦИИ