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

поиска
Содержание

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

эффективным ни был выбранный вами алгоритм, но если в качестве

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

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

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

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

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

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

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

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

сложность O(N2)

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

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

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

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

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

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

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

1-ый проход

2-ой проход

3-ий проход

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

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

for

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

integer;
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] уже поставлены

j раз (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;

i + 1;
flag := False; { сбросить флаг }

i := 0;

i

i := i + 1;

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

begin
nMin = i ;
for j:= i+1 to N

N-1

N

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

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

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

i+1

i

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

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

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

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

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

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

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

if a[i-1]>a[i] then begin
a[0]:= a[i]; {*}

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

случай, когда на вход подается уже упорядоченная последовательность данных. Тогда

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

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

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

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

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

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

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

становиться левый центральный элемент. Это соответствует вычислению номера "середины" по

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

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

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

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

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

же произойдет, если мы станем искать позицию для единицы:
[2 4

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

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

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

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

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

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

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

Необходимо,

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

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

состоит в том, что она рассматривает весь список как совокупность

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

упорядочиваются элементы n/2 пар (A[i], А[n/2 + i]) для 1

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

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

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

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

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

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

списку.
Сортировка Шелла

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

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

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

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

сортировку простым выбором.

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

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

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

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

структуру:
Видно, что любой элемент a[i] (1

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

div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не

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

1 do begin
j:=i;
while j

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

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

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

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

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

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

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

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

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

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

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

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

for i:= N downto 2 do begin
x:=a[1]; a[1]:=a[i]; a[i]:=x;
j:= 1; flag:=true;
while (j<=((i-1)div 2)) and flag do begin
k:=2*j;
if (k+1<=i-1) and (a[k] k:= k+1;
if a[k]>a[j] then begin
x:=a[j]; a[j]:=a[k]; a[k]:= x;
j:= k end
else flag:=false
end
end;

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

пирамиду:
[12, 11, 8, 7, 10, 6, 5, 4, 2,

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

8, 7, 10, 6, 5, 4, 2, 9, 3], 12;
2)

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

7, 3, 6, 5, 4, 2], 10, 11, 12;
6) Просеиваем

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

7, 3, 6, 5, 4, 2], 10, 11, 12;
6) Просеиваем

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

4, 3, 2, 5], 8, 9, 10, 11, 12;
10) Просеиваем

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

1, 3], 6, 7, 8, 9, 10, 11, 12;
14) Просеиваем

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

4, 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

integer);
var L, R, c, X: integer;
begin
if first < last

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

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;

разделение

обмен

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

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

A: array[1..N] of integer;


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

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

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

if A[i] = 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;

> 6
Выбрать средний элемент A[c] и сравнить с X.
Если X

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

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;

нашли

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

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