Форум АНТИЧАТ - Показать сообщение отдельно - Оценка эффективности и быстродействия различных алгоритмов.

1. Псевдокод.

Код:

ShellSort(list, N)
list//массив элементов
N//количество элементов в массиве
passes = log2(N);
while (passes >= 1)  do
     increment = 2^(passes-1) – 1;
     for start = 1 to increment do
          InsertSort(list, N, start, increment)//сортировка полученного набора методом вставки
     end for;
end while.

2. Оценка эффективности.

В худшем случае:

Код:

T(n) = O(N^(3/2))

3. Вывод.

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
-отсутствие потребности в памяти под стек
-отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(N^2), что хуже, чем худшее гарантированное время для сортировки Шелла

Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов. (с) Wikipedia