Алгоритмы сортировки. Shell Sort

Shell Sort один из самых загадочных алгоритмов. Являясь модификацией обычного Insertion Sort — все же нет точного доказательства его оптимальности в различных ситуациях. Вернее конфигурация алгоритма, которая однозначно бы говорила что больше из него не выжать — на даный момент однозначного ответеа нет.

Shell Sort — это тот же самый Insertion Sort, но перед сортировкой с помощью Insertion Sort, мы проводим “грубый” проход. Грубый проход — это сравнение элементов, которые находяться на расстоянии D. После этого сравниваются элементы которые находятся на меньшем расстоянии, и так, пока D=1, что является заключительной проверкой, после которой мы имеем отсортированный массив. Как помните из статьи об Insertion Sort сортировка проходит практически мгновенно, в случае если массив частично отсортирован.

Итак, в чем же неопределнность? Неопределенность, именно в этом самом выборе расстояния D между двумя числами.

Есть огромное количество методов выбора числа D:

  1. Самый просто пример это D = n / 2, D2 = D /2 … Dn =1 . В худшем случае сложность алогритма O(n) = N ^ 2
  2. Предложение Хиббарда: проверить на всем N ^i — 1<= N. В таком случае сложность алгоритма O(n) = n ^ (3/2)
  3. Числа Седжвика и много много другого

Для примера я возьму метод Кнута: (3^k -1) / 2, так как их достаточно легко сгенерить☺

var shell_sort = function(array){
var length = array.length;
var h = 1;
while( h < length / 3){
h = 3 * h + 1;
}
  while( h > 0 ){
for ( var i = h; i < length; i++){
      for ( var j = i; j > 0 && array[j] < array[j-h]; j-=h){
array.swap(j, j-h);
}
}
//decreasing h
h = — h / 3
  }
return array;
};

Как видим, в самом начале мы определяем h. После чего, начинаем прочесывать числа на различном расстоянии, при этом после каждой итерации уменьшать h. Числа Кнута в результате дают сложность алгоритма равную O(n) = n^(3/2)

А теперь — самое интересное! Результаты:

Внимательные читатель заметит, что для того чтоб показать хоть какие-то цифры, добавилась еще одна строчка, с 1000000 ( 1 миллион ) элементами.

Потому, если кто-то вас спросит какая разница, или алгоритм работает со O(n) = n ^ 2 или O(n) = N^ (3/2) ( вряд ли именно такое число спросят ☺ )просто покажите эти две картинки. Картинка обычного Insertion Sort так, чисто для памяти прилагается:

Исходники примеров вы можете найти тут.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.