Методы сортировки
Для решения многих задач необходимо упорядочить исходные данные по определенному признаку. Процесс такого упорядочения называется сортировкой.
Цель сортировки – облегчить последующий поиск элементов в таком упорядоченном массиве.
Порядок, при котором в массиве первым элементом является самое маленькое число, а каждое следующее больше предыдущего, а последнее – самое большое из чисел данного массива называют возрастающим. Прямо противоположный порядок – убывающим.
Простые, однако, более медленные методы сортировки:
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].