Введение в алгоритм сортировки оболочки

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

Затем подсписки сортируются с использованием сортировки вставкой, после чего они объединяются. Объединенный список не полностью отсортирован, но дает алгоритму преимущество, заключающееся в том, что элементы находятся ближе к их конечным позициям.

Сортировка вставкой снова используется для окончательной сортировки списка.

Более пристальный взгляд на сортировку по оболочке

Приведенное выше описание могло не иметь большого смысла, но пример должен помочь. Предположим, у вас есть список: [39, 6, 2, 51, 30, 42, 7, 4, 16] и значение пробела, равное трем.

В первом подсписке будут элементы: 39, 51, 7.

Второй подсписок: 6, 30, 4

Третий и последний подсписок: 2, 42, 16

После сортировки вставкой каждый из подсписок будет упорядочен, как показано ниже:

Первый: 7, 39, 51

Второй: 4, 6, 30

Третий: 2, 16, 42

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

Связанный: Введение в алгоритм пузырьковой сортировки

Таким образом, вы получите следующую последовательность:

[7, 4, 2, 39, 6, 16, 51, 30, 42]

Обратите внимание, что список еще не отсортирован, но элементы находятся ближе к позициям, в которых они должны находиться. После выполнения сортировки вставкой для этой комбинации списков, список будет окончательно отсортирован:

[2, 4, 6, 7, 16, 30, 39, 42, 51]

Анализ алгоритмов

Сложность сортировки по оболочке составляет от O (n) до O (n2). Расчет для этого вывода выходит за рамки данной статьи.

Реализация Python:

 def shellSort(my_list):
 n = len(my_list)
 interval = n // 2 # floor division
 while interval > 0:
 for val in range(interval, n):
 temp = my_list[val]
 x = val
 while x >= interval and my_list[x - interval] > temp:
 my_list[x] = my_list[x - interval]
 x = x - interval

 my_list[x] = temp
 interval = interval // 2

Переход к сортировке слиянием

Есть несколько алгоритмов сортировки, каждый из которых работает по-своему. Например, сортировка слиянием использует стратегию «разделяй и властвуй» и имеет сложность O (nlogn).

Сортировка слиянием в некоторых случаях лучше, чем сортировка оболочки, и на нее определенно стоит обратить внимание. Он должен быть следующим в вашем списке чтения алгоритмов сортировки.