воскресенье, 19 сентября 2010 г.

Сортировка Шелла (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 элементов сортировка Шелла сортирует не хуже пирамидальной сортировки. Но в общем случае давайте будем считать, что сортировка Шелла имеет для нас только академический интерес

Комментариев нет:

Отправить комментарий