Смысл использования быстрой сортировки – массив из 1 миллиона элементов пузырьковой сортируется 6 минут, а быстрой 7 секунд

Методы сортировки

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

Цель сортировки – облегчить последующий поиск элементов в таком упорядоченном массиве.

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

Простые, однако, более медленные методы сортировки:

1. сортировка методом простого выбора;

2. сортировка методом простого обмена (пузырьковая сортировка) – простой в запоминании, но слишком долгий по времени;

3. сортировка методом простых вставок (метод прямого включения) – время чуть меньше пузырьковой, избегает пустых проходов, чуть быстрее пузырьковой.

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

Сущность метода:

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

 

Демонстрация метода (сортировка по возрастанию):

Исходный массив	2	-3	4	0	3
	2	-3	3	0	4
	2	-3	0	3	4
	0	-3	2	3	4
Искомый массив	-3	0	2	3	4

 

!!! Красным выделены элементы, которые исключаются из рассмотрения.

 

Алгоритм сортировки выбором:

For i:=n downto 2 do begin

    k:=i;

    max:=a[i];

    For j:=1 to i-1 do if a[j]>max then begin

                                                             max:=a[j];

                                                             k:=j

                                                             End;

    a[k]:=a[i];

    a[i]:=max

End;

Сортировка обменом – учим этот способ сортировки!!!

Сущность метода:

Если два элемента массива расположены не по порядку, то они меняются местами. Процесс повторяется до тех пор, пока элементы не будут упорядочены.

 

Демонстрация метода (сортировка по возрастанию):

Исходный массив	0	5	6	3	4	2	9	1
	0	5	3	4	2	6	1	9
	0	3	4	2	5	1	6	9
	0	3	2	4	1	5	6	9
	0	2	3	1	4	5	6	9
	0	2	1	3	4	5	6	9
Искомый массив	0	1	2	3	4	5	6	9

 

Алгоритм сортировки обменом:

For i:=1 to n-1 do

  For j:=1 to n-i do if a[j]>a[j+1] then begin

x:=a[j];

a[j]:=a[j+1];

a[j+1]:=x

end;

 

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

Сортировка этим методом заключается в следующем: на i-м шаге считается, что часть массива, содержащая первые i-1 элементов, уже упорядочена, т. е.
A[1] ≤ A[2] ≤ … ≤ A[i-1] (для сортировки по неубыванию). Далее берётся i-й элемент, и для него подбирается место  в отсортированной части массива, такое, что после его вставки упорядоченность не нарушается. Затем выполняется вставка элемента A[i] на найденное место. На каждом шаге отсортированная часть массива увеличивается.

 

 

Рассмотрим на примере:

 

Смысл использования быстрой сортировки – массив из 1 миллиона элементов пузырьковой сортируется 6 минут, а быстрой 7 секунд.

УЧИМ ЭТОТ СПОСОБ СОРТИРОВКИ!!!

 

Приведем модификацию процедуры быстрой сортировки из книги Н. Вирта. Это рекурсивная схема реализации, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива.

ВНИМАНИЕ! Вместо команды x:=a[(m+t) div 2] рекомендуется использовать x:=a[random(t-m+1) + m].