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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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

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

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

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] на найденное место. На каждом шаге отсортированная часть массива увеличивается.

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