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

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

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