Урок 21. Сортировка массива

1. Сортировка массива
Сортировка массива - это расстановка элементов массива в заданном порядке (самое простое - по возрастанию или убыванию).
Существующие методы сортировки массива по возрастанию/убыванию:

• метод пузырька
• метод выбора
• "быстрая сортировка"
• сортировка "кучей"
• сортировка слиянием
• пирамидальная сортировка

2. Метод пузырька
Как пузырей воздуха поднимается со дна вверх в стакане воды, так самый маленький "легкий элемент" массива перемещается вверх (к началу массива) - всплывает.


Задача: сортировка массива по возрастанию (array112 стр. 59).


Алгоритм: начиная снизу (с конца массива), сравниваем два соседних элемента, если они стоят "неправильно", то меняем их местами.

За один проход на месте A[1] будет стоять минимальный элемент:
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 2 do
if A[j]>A[j+1] then begin  c:= A[j]; A[j]:=A[j+1]; A[j+1]:=c end;
...


i-ый проход: 
for  j:=n-1 downto i do

Задача для самостоятельного решения: отсортировать массив в порядке возрастания последней цифры.

3. Метод простого выбора

Задача array113. Идея следующая: найти максимальный элемент массива и поменять его местами с последним (N-м) элементом; выполнить описанные действия N-1 раз, каждый раз уменьшая на 1 количество анализируемых элементов и выводя содержимое массива.

Первый проход:
nmin:=1;
for  j:=2 to n do
if A[j]>A[nmin] then nmin:=j;
if nmin<>1 then begin c:=A[1]; A[1]:=A[nmin];A[nmin]:=c end;


Второй проход:
nmin:=2;
for  j:=3 to n do
if A[j]>A[nmin] then nmin:=j;
if nmin<>2 then begin c:=A[2]; A[2]:=A[nmin];A[nmin]:=c end;
...


i-ый проход:
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;


Задача для самостоятельного решения: отсортировать массив в порядке возрастания суммы цифр. Массив заполнить двузначными числами, например числами от 10 до 99.


4. Домашнее задание
На основе метода пузырька решите задачу array115.