Сортировка Шелла (Shell_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Визуализатор: rain.ifmo.ru  [Java]

Реализация:
Данная сортировка является модификацией сортировки вставками.
На начальных этапах происходит сортировка вставками элементов, которые имеют индексы: base, base + d, base + 2*d,… base + n*d, где base – индекс первого элемента в рассматриваемой подпоследовательности массива, d – фиксированный шаг, n – некоторое натуральное число, такое что индекс base + n*d не выходит за границы массива. Постепенно уменьшаем d, до тех пор пока оно не станет равным 1. И на последней итерации происходит сортировка вставками всего массива.

1. void shell_sort(vector<int> &mas)
2. {
3.   int d[] = {1750,701,301,132,57,23,10,4,1,0};
4.   int posD = 0;
5.   while (d[posD]!=0)
6.   {
7.     int curD = d[posD];
8.     for (int i=curD;i<mas.size();i++)
9.     {
10.       int value = mas[i];
11.       int j = i - curD;
12.       for (;j>=0;j-=curD)
13.       {
14.         if (mas[j]<=value)
15.           break;
16.         mas[j+curD] = mas[j];
17.       }
18.       mas[j+curD] = value;
19.     }
20.     posD++;
21.   }
22. }

* This source code was highlighted with Source Code Highlighter.

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