Задача: Сортировка Шелла, оптимальный выбор приращений
Исходник: Сортировка Шелла с приращениями для больших размерностей и последним "пузырьковом" проходе, язык: C++ [code #21, hits: 7246]
автор: this [добавлен: 31.01.2006]
  1. /* Рассчитывает последовательность
  2. приращений рекомендуюмую при больших
  3. размерах сортируемой последовательности */
  4. int DForBigN(int d[], long n) {
  5. int i = 0;
  6. d[i] = 1;
  7.  
  8. do {
  9. i++;
  10. d[i] = 3*d[i-1] + 1;
  11. } while (d[i] < n);
  12.  
  13. return (i < 2) ? 0 : i-2;
  14. }
  15.  
  16.  
  17.  
  18. template<class T>
  19. void ShellSortDForBigN(T* x) {
  20. /* максимальное количество рассчитываемых
  21. приращений = 20 */
  22. int d, i, j, dseq[20];
  23. int di;
  24.  
  25. /* Рассчитываем последовательность
  26. приращений */
  27. di = DForBigN(dseq, n);
  28.  
  29. while (di >= 0) {
  30. /* Приращение на данном шаге */
  31. d = dseq[di--];
  32.  
  33. /* этот цикл делает проход "пузырька" в том числе и
  34. для последней последовательности, когда d=1, поэтому
  35. вызывать в конце InsertSort или какую-либо другую
  36. элементарную сортировку - не требуется */
  37. for (i = d; i < n; i++) {
  38. T tmp = x[i];
  39. for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
  40. x[j+d] = x[j];
  41. }
  42. x[j+d] = tmp;
  43. }
  44. }
  45. /* Не требуется вызывать InsertSort или BubbleSort
  46. т.е. ко всей последовательности во вложенном цикле
  47. уже был применен метод пузырька */
  48. }
Реализует алгоритм сортировки Шелла.
Значения приращений рассчитываются методом, рекомендуемым при больших размерностях сортируемой последовательности.
Следует обратить внимание на то, что этот алгоритм является также интересной вариацией алгоритмов Шелла: в конце не нужно ко всей последовательности применять какую-либо элементарную сортировку(вставкой, выбором, пузырьком и проч.), поскольку внутренний цикл осуществляет проход пузырькового метода в том числе и для конечной последовательности, когда d=1.

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

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