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

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

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