Идея сортировки
Shell Sort - это по сути просто усовершенствование алгоритма Insertion Sort.
Суть в том, чтобы повторить Insertion Sort несколько раз, только сравнивать не рядом стоящие элементы, а элементы стоящие друг от друга на расстоянии d, которое будет изменяться на каждой итерации определённым образом. Существует несколько способов выбора значений для d, но в этой статье представлен один способ - деление расстояния d на 2.
Стоит заметить, что при d = 1 - будут сравниваться рядом стоящие элементы, как и в обычном Insertion Sort. Однако в Shell Sort, перед тем, как d станет равным 1, мы уже передвинем некоторые элементы ближе к тем местам, где они должны стоять в отсортированном массиве. Тем самым минимизировав количество сравнений, а значит уменьшив время работы сортировки.
Время работы | Сложность
В худшем случае - O(N * (log N)^2)
Реализация сортировки
Код на c++:
Код на c:
