Задача: Сравнение алгоритмов быстрой сортировки
Исходник: QuickSort4.cpp, язык: C++ [code #57, hits: 10070]
автор: this [добавлен: 18.02.2006]
  1. #include "QuickSort4.h"
  2. #include "time.h";
  3.  
  4. QuickSort4::QuickSort4(int n, int* x, int cutoff) : QuickSort(n, x) {
  5. this->algName = "Quick Sort [Rand Choice] Optimized";
  6. this->cutoff = cutoff;
  7. }
  8.  
  9. void QuickSort4::Run(void)
  10. {
  11. this->Launch(0, (this->n - 1));
  12.  
  13. // Заключительная сортировка вставкой
  14. this->simpleSortObj.setArr(this->x);
  15. this->simpleSortObj.setSize(this->n);
  16. this->simpleSortObj.Run();
  17.  
  18. // Не забываем посчитать swap-ы сделанные им
  19. this->swapNum += this->simpleSortObj.getSwapNum();
  20. }
  21.  
  22. void QuickSort4::Launch(int l, int u) {
  23. if (u - l < this->cutoff)
  24. return;
  25.  
  26. this->Swap(l, this->GetRand(l, u));
  27. int t;
  28. int i,j;
  29. t = this->x[l]; i = l; j = u+1;
  30.  
  31. while (1) {
  32. /* пропуск элементов справа и слева,
  33. чтобы не делать лишней работы */
  34. do i++; while (i <= u && this->x[i] < t);
  35. do j--; while (this->x[j] > t);
  36.  
  37. if (i > j)
  38. break;
  39. // Делаем swap(i, j):
  40. int tmp;
  41. tmp = this->x[i]; this->x[i] = this->x[j]; this->x[j] = tmp;
  42. this->CountSwap();
  43. }
  44.  
  45. this->Swap(l, j);
  46.  
  47.  
  48. this->Launch(l, j-1);
  49. this->Launch(j+1, u);
  50. }
  51.  
  52. int QuickSort4::GetRand(int l, int u)
  53. {
  54. srand(time(NULL));
  55. return l + rand() % (u-l + 1);
  56. }
  57.  
  58. unsigned int QuickSort4::getCutoff(void)
  59. {
  60. return this->cutoff;
  61. }
  62.  
  63. void QuickSort4::setCutoff(unsigned int cutoff)
  64. {
  65. this->cutoff = cutoff;
  66. }
  67.  
  68. QuickSort4::~QuickSort4(void)
  69. {
  70. }
  71.  
QuickSort4.cpp :: Реализация класса быстрой сортировки QSort4 [опорный элемент первый, пропуск одинаковых +cutoff]

Заголовочный файл: QuickSort4.h
Функция аналог: QSort4

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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