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

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

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

Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С * N 2 действий, где С - некоторая константа. Этот факт принято обозначать следующей символикой: O ( N 2 ).

Сортировка

Алгоритмы:

• простые и понятные, но неэффективные для больших массивов
• простые и понятные, но неэффективные для больших массивов

• метод пузырька метод выбора Метод вставка
• метод пузырька метод выбора Метод вставка
• метод пузырька
• метод выбора
• Метод вставка

• сложные, но эффективные
• сложные, но эффективные

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

сложность O( N 2 )

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

O( N 2 )

время

O( N · log N )

N

5

5

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

Покажем этот метод на примере сортировки массива А(5).

А

индекс элемента

1

2

4

3

3

4

2

1

значение элемента

пример:

4

3

4

4

1

1

1

2

2

2

4

3

1

2

Вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз – до тех пор , пока не найдем место куда нужно вставить число 3.

1

3

4

2

3

3

3

4

4

4

1

2

2

2

Этот процесс продолжается для числа 1.

1

2

3

4

1

1

3

4

3

4

1

3

4

2

Завершаем сортировку, поместив число 2 на нужное место.

Постановка задачи:

Дано:

неупорядоченный числовой массив;

A – имя массива;

n - размер массива;

i – индекс элемента;

m – элемент массива, с которым работаем (начиная

со второго);

k – индекс элемента, стоящего перед элементом m .

Требуется:

упорядочить числовой массив по возрастанию.

=1) AND a(k)m a(k+1)=a(k) k=k-1 WEND a(k+1)=m NEXT i " width="640"

FOR i = 2 TO n

m=a(i)

k=i-1

WHILE (k=1) AND a(k)m

a(k+1)=a(k)

k=k-1

WEND

a(k+1)=m

NEXT i

МЕТОД В ЖИЗНИ:

В обычной жизни мы сталкиваемся с этим методом при игре в карты. Большинство картежников, сами того не сознавая, пользуются именно таким методом сортировки для упорядочения пришедших им карт. Когда игрок получает очередную карту, все предыдущие уже отсортированы, поэтому он просто вставляет ее в нужное место.

ПРЕИМУЩЕСТВА:

• прост в реализации;

• не требует дополнительной памяти;
• эффективен на небольших наборах данных;
• эффективен на наборах данных, которые уже частично отсортированы;
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• может сортировать список по мере его получения.

Основной недостаток :

необходимость многократного сдвига элементов.

Метод пузырька

Идея – пузырек воздуха в стакане воды поднимается со дна вверх.

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

1-ый проход

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

5

1

2

3

5

2

1

3

5

1

2

5

1

2

3

3

2-ой проход

3-ий проход

1

2

5

3

1

2

3

5

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

1

5

2

3

1

1

2

5

5

2

3

3

A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 1 2 -ой проход ! A[1] уже на своем месте! 1 2 … N-1 N 1 5 … 3 6 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; i -ый проход for j:=N-1 downto i do ... i © С.В.Кухта, 2009 " width="640"

Программа

1-ый проход :

сравниваются пары

A[N-1] и A[N], A[N-2] и A[N-1]

…

A[1] и A[2]

A[j] и A[j+1]

1

2

…

N-1

N

5

2

…

6

3

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

2 -ой проход

!

A[1] уже на своем месте!

1

2

…

N-1

N

1

5

…

3

6

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;

i -ый проход

for j:=N-1 downto i do

...

i

© С.В.Кухта, 2009

A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с ; end; end; i © С.В.Кухта, 2009 16 16 " width="640"

Программа

program qq;

const N = 10;

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

i, j, c: integer;

begin

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

{ вывести исходный массив }

{ вывести полученный массив }

end.

?

Почему цикл по i до N-1 ?

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

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

© С.В.Кухта, 2009

16

16

16

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

Внешний цикл выполнился n –1 раз. Внутренний цикл выполняется j раз ( K = n –2, n –1, ..., 1 ).

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

C ( n ) =1+2+ ...+ n –1 = n *( n –1)/2,

M ( n ) = n *( n –1)/2 .

В худшем случае (когда элементы исходного массива расположены в порядке убывания)

C ( n ) = n *( n –1)/2= O ( n 2 ),

M ( n ) = n *( n –1)/2= O ( n 2 ).

16

16

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; 18 18 " width="640"

16

Метод пузырька с флажком

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

Реализация: переменная-флаг , показывающая, был ли обмен ; если она равна False , то выход.

2

1

2

1

3

4

4

3

var flag: boolean;

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;

18

18

A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с ; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; i := i + 1; i 18 18 " width="640"

18

Метод пузырька с флажком

i := 0;

repeat

i := i + 1;

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 }

i := 0;

i := i + 1;

i

18

18

18

Метод выбора

Идея:

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

1

2

4

3

4

3

1

2

1

2

3

4

1

3

4

2

Метод выбора

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

for i := 1 to N-1 do begin

nMin = i ;

for j:= i+1 to N do

if A[j]

if nMin i then begin

c:=A[i];

A[i]:=A[nMin];

A[nMin]:=c;

end;

end;

N-1

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

i

N

i+1

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

?

Можно ли убрать if ?

21

21

Далее материал для любознательных ))

21

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

Необходимо, однако, отметить, что на небольших наборах сортируемых данных ( N

• выигрыш становится заметным только при больших N .
• выигрыш становится заметным только при больших N .

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

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

Эта сортировка базируется на уже известном нам алгоритме простых вставок.

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

Эти разбиения помогают сократить количество пересылок:

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

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

Сортирует элементы массива А[1.. n ] следующим образом: