Задача: Сравнение алгоритмов сортировки массива
Исходник: ShellSortSedj1.cpp, язык: C++ [code #38, hits: 12283]
автор: this [добавлен: 18.02.2006]
  1. #include "ShellSortSedj1.h"
  2.  
  3. ShellSortSedj1::ShellSortSedj1(int n, int* x, int maxIncNum, bool getIncs) : ShellSort(n, x) {
  4. this->algName = "Shell Sort [Sejvick, Without InsertSort]";
  5.  
  6. // Рассчитываем таблицу приращений
  7. if (getIncs) {
  8. this->dseq = new int[maxIncNum];
  9. this->di = this->GetIncrements();
  10. }
  11. }
  12.  
  13. int ShellSortSedj1::GetIncrements(void) {
  14. int p1, p2, p3, i;
  15.  
  16. p1 = p2 = p3 = 1;
  17. i = -1;
  18. do {
  19. if (++i % 2) {
  20. this->dseq[i] = 8*p1 - 6*p2 + 1;
  21. } else {
  22. this->dseq[i] = 9*p1 - 9*p3 + 1;
  23. p2 *= 2;
  24. p3 *= 2;
  25. }
  26. p1 *= 2;
  27. } while(3*this->dseq[i] < this->n);
  28.  
  29. return (i > 0) ? --i : 0;
  30. }
  31.  
  32. void ShellSortSedj1::Run(void) {
  33. /* максимальное количество рассчитываемых
  34. приращений = 20(хватит более чем достаточно) */
  35. int d, i, j;
  36. int _di = this->di;
  37. while (_di >= 0) {
  38. /* Приращение на данном шаге */
  39. d = this->dseq[ _di-- ];
  40.  
  41. /* этот цикл делает проход "пузырька" в том числе и
  42. для последней последовательности, когда d=1, поэтому
  43. вызывать в конце InsertSort или какую-либо другую
  44. элементарную сортировку - не требуется */
  45. for (i = d; i < this->n; i++) {
  46. int tmp = this->x[i];
  47. for (j = i-d; (j >= 0) && (this->x[j] > tmp); j -= d) {
  48. this->x[j+d] = this->x[j];
  49. this->CountSwap();
  50. }
  51. x[j+d] = tmp;
  52. this->CountSwap();
  53. }
  54. }
  55. /* Не требуется вызывать InsertSort или BubbleSort
  56. т.е. ко всей последовательности во вложенном цикле
  57. уже был применен метод пузырька */
  58. }
  59.  
  60. int ShellSortSedj1::GetInc(int incNum) {
  61. return this->dseq[ incNum ];
  62. }
  63.  
  64. ShellSortSedj1::~ShellSortSedj1(void)
  65. {
  66. }
  67.  
ShellSortSedj1.cpp :: Реализация класса сортировки Шелла

Значения приращений рассчитываются методом Р. Седжвика.
Без последнего результирующего пузырькового прохода.

Заголовочный файл: ShellSortSedj1.h
Функция-аналог: тут
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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