Задача: Сортировка Шелла, обший принцип
Исходник: Базовая сортировка Шелла без результирующей сортировки, язык: C++ [code #24, hits: 8629]
автор: this [добавлен: 31.01.2006]
  1. template<class T>
  2. void ShellSortBin2(T* x) {
  3. int d = n, i, j;
  4. while (d > 0) {
  5. d /= 2;
  6.  
  7. /* Данный цикл представляет собой
  8. 1 "пузырьковый" проход по всем группам элементов
  9. на данном шаге. Кроме того, здесь, он выполняется
  10. и в конце, когда d=1, позволяя избежать результирующей
  11. сортировки */
  12. for (i = d; i < n; i++) {
  13. T tmp = x[i];
  14. for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
  15. x[j+d] = x[j];
  16. }
  17. x[j+d] = tmp;
  18. }
  19. }
  20. }
Приращение на каждом шаге - уменьшается вдвое.
Результирующая сортировка не выполняется поскольку для конечной последовательности Шелла, т.е. когда d=1 и имеются 2 отсортированные группы элементов - к этой последовательности был также применен проход "пузырька", окончательно расставляющий элементы по своим местам.

Производительность: менее ~ O(n2)
Расход памяти: - (только на счетчики цикла, доп. переменные и проч.)
При этом следует отметить, что расход памяти меньше чем в базовом варианте, т.к. не запускается фукнция результирующей сортировки и swap также не используется.
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию