Презентация на тему Алгоритмы внутренней сортировки. (Тема 1.2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1-ый проход

2-ой проход

3-ий проход

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

A[N-2] и A[N-1]
…
A[1] и A[2]
A[j]

2-ой проход

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;

1

i-ый проход

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

i

array[1..N] of 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-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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

структуру:
Видно, что любой элемент 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-й шаг: Превратить исходный массив в

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

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

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,

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

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

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

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 элементов,
то первая часть

Сортировка слиянием

last: integer);
Var c: integer;
begin
if first last then

В программе используется процедура Merge(A, first, c, last ), которая выполняет слияние двух отсортированных частей массива A таким образом, чтобы сохранилась упорядоченность элементов в результирующем массиве.

integer);
Var B: Massiv;
i, j, k: integer;
begin
i:=first;

(j

элементы, расположенные дальше друг от друга.
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

Massiv; first, last: integer);
var L, R, c, X: integer;
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;

разделение

обмен

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

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

massiv=array[1..N] of integer;
var A:massiv;



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

procedure QuickSort ( var A: massiv: first, last: integer);
...