Сортировка массивов

величины возникает в программировании очень часто. К примеру, входные данные

был выбранный вами алгоритм, но если в качестве подзадачи он

только файлами).
В этой Теме рассматриваются только внутренние методы сортировки.
Их

порядке: по возрастанию, убыванию, последней цифре, сумме делителей, … .

Под сортировкой последовательности понимают процесс перестановки элементов последовательности в определенном порядке: по возрастанию, убыванию, последней цифре, сумме делителей, … .

Пусть дана последовательность элементов a1, a2, ... , an.
Элементы этой последовательности – данные произвольного типа, на котором определено отношение порядка “<” (меньше) такое, что любые два различных элемента сравнимы между собой.
Сортировка означает перестановку элементов последовательности ak1, ak2, ... , akn такую, что
ak1 < ak2 < ... < akn.

и экономное использование памяти.
Это означает, что алгоритм не должен

размерности входных данных.
Иными словами, при сортировке массива, состоящего из

Простые сортировки

но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка
сложность

сложность O(N·logN)

зависит не только от длины этой последовательности, но и от

Простые сортировки

по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих

Простые сортировки

дна вверх.
Для массивов – самый маленький («легкий» элемент перемещается

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

…
A[1] и A[2]
A[j] и A[j+1]
2-ой проход

for j:=N-1 downto

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;

1

i-ый проход

for j:=N-1 downto i do
...

i

i, j, c: integer;
begin
{ заполнить массив }
{ вывести

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;
end;

i

элементы выше A[i] уже поставлены

(K = n–2, n–1, ..., 1).
Каждое выполнение тела внутреннего

Эффективность метода пузырька

не было обменов, массив уже отсортирован и остальные проходы не

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;

1;
flag := False; { сбросить флаг }
for j:=N-1

i := 0;

i

i := i + 1;

местами с A[1])
из оставшихся найти минимальный элемент и поставить на

= i ;
for j:= i+1 to N do

N-1

N

нужно N-1 проходов

поиск минимального от A[i] до A[N]

если нужно, переставляем

i+1

i

упорядочение данных по мере их поступления.
В этом случае при

Сортировка простыми вставками

вводимых данных, для каждого нового ее элемента выполнять следующие действия:

Сортировка простыми вставками

if a[i-1]>a[i] then begin {*}

нулевой компонентой (это следует сделать в разделе описаний var) и

Метод прямых вставок с барьером

then begin
a[0]:= a[i]; {*}
j:=

Метод прямых вставок с барьером

на вход подается уже упорядоченная последовательность данных. Тогда алгоритм совершит

Метод прямых вставок с барьером

3 6 2 1
Выполняя алгоритм, получим такие результаты (подчеркнута уже

Метод прямых вставок с барьером

упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный

Сортировка бинарными вставками

таком массиве:
[2 4 6 8 10 12 14 16 18]

Сортировка бинарными вставками

центральный элемент. Это соответствует вычислению номера "середины" по формуле
nomer_sred:= (nomer_lev

Сортировка бинарными вставками

позицию не для семерки, а для девятки, то последовательность границ

Сортировка бинарными вставками

пор, пока левая граница не окажется правее (!) правой границы.

Сортировка бинарными вставками

если мы станем искать позицию для единицы:
[2 4 6 8]

Сортировка бинарными вставками

[12 14 16 18]
2 4 6 8 10 12 14

Сортировка бинарными вставками

a[i-1]>a[i] then begin
x:= a[i];
left:= 1; right:=

проверок, что уже значительно лучше (для примера, сравните 1000 и

Сортировка бинарными вставками

сортировкам относятся алгоритмы с общей сложностью O(N*logN).

Необходимо, однако, отметить,

Смысл ее состоит в раздельной сортировке методом простых вставок нескольких

Сортировка Шелла

том, что она рассматривает весь список как совокупность перемешанных подсписков.

Сортировка Шелла

n/2 пар (A[i], А[n/2 + i]) для 1 < i

Сортировка Шелла

каждом, в которых
первый подсписок содержит первый и девятый элементы,

Сортировка Шелла

элемента в каждом:
первый подсписок на этот раз содержит первый,

Сортировка Шелла

нечетными и четными номерами соответственно.
Сортировка Шелла

for i:=incr+1 to n do begin
j:= i-incr;
while j>0

Сортировка Шелла

на нем останавливаться.
Было доказано, что сложность этого алгоритма в

Сортировка Шелла

выбором.

Р.Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное

Пирамидальная сортировка

в пирамиду, где каждый элемент "опирается" на два меньших.

Этот

Пирамидальная сортировка: просеивание

что любой элемент a[i] (1

Пирамидальная сортировка: просеивание

по N-й) являются основанием пирамиды, их просеивать не нужно.
А

Пирамидальная сортировка: просеивание

begin
j:=i;
while j

таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):
Пирамидальная сортировка
Пирамидальная

вниз не производится
Пирамидальная сортировка: просеивание

и 2; перестановка не требуется
Пирамидальная сортировка: просеивание

1 и 8
производится проверка пары элементов 1 и 6; требуется

перестановка элементов 1 и 12

Пирамидальная сортировка: просеивание

a[i], a[2*i] и a[2*i+1] максимум находится "сверху".
Пирамидальная сортировка: просеивание

последовательность действий:
0-й шаг: Превратить исходный массив в пирамиду (с помощью

Пирамидальная сортировка: алгоритм

поэтому здесь приведена только реализацией основного шага 1:
for i:=

11, 8, 7, 10, 6, 5, 4, 2, 9, 3,

Пирамидальная сортировка: пример

10, 6, 5, 4, 2, 9, 3], 12;
2) Просеивая элемент

Пирамидальная сортировка: пример

6, 5, 4, 2], 10, 11, 12;
6) Просеиваем элемент a[1]:
[9,

Пирамидальная сортировка: пример

6, 5, 4, 2], 10, 11, 12;
6) Просеиваем элемент a[1]:
[9,

Пирамидальная сортировка: пример

2, 5], 8, 9, 10, 11, 12;
10) Просеиваем элемент a[1]:
[7,

Пирамидальная сортировка: пример

6, 7, 8, 9, 10, 11, 12;
14) Просеиваем элемент a[1]:
[5,

Пирамидальная сортировка: пример

6, 7, 8, 9, 10, 11, 12;
20) Просеивать уже ничего

Пирамидальная сортировка: пример

на маленьких примерах (N

Пирамидальная сортировка

дальше друг от друга.
N div 2
2 шаг: переставить элементы

1 шаг: выбрать некоторый элемент массива X

3 шаг: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

и справа от него в отсортированном массиве стоит одинаковое число

Разделение:
выбрать средний элемент массива (X=67)


установить L:=1, R:=N
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L<=R, поменять местами A[L] и A[R] и перейти к п. 3

R, c, X: integer;
begin
if first < last then begin

ограничение рекурсии

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;
end;

разделение

обмен

двигаемся дальше

сортируем две части

of integer;


begin
{ заполнить массив }
{ вывести исходный массив

procedure QSort ( first, last: integer);
...

или установить, что его нет.
Решение: для произвольного массива: линейный

= X then begin
nX := i;

nX := 0; { пока не нашли ...}



if nX < 1 then writeln('Не нашли...')
else writeln('A[', nX, ']=', X);

nX – номер нужного элемента в массиве

Улучшение: после того, как нашли X, выходим из цикла.

for i:=1 to N do { цикл по всем элементам }
if A[i] = X then { если нашли, то ... }
nX := i; { ... запомнили номер}

nX := 0; i := 1;
while i <= N do begin
if A[i] = X then begin
nX := i; i := N;
end;
i := i + 1;
end;

break;

i := N;

средний элемент A[c] и сравнить с X.
Если X = A[c],

:= N; {границы: ищем от A[1] до A[N] }









if

while R >= L do begin
c := (R + L) div 2;




if X < A[c] then R := c - 1;
if X > A[c] then L := c + 1;
end;

номер среднего элемента

if X = A[c] then begin
nX := c;
R := L - 1; { break; }
end;

нашли

выйти из цикла

сдвигаем границы