Задача: Сравнение алгоритмов быстрой сортировки
Исходник: QuickSort3.cpp, язык: C++ [code #55, hits: 11503]
автор: this [добавлен: 18.02.2006]
  1. #include "QuickSort3.h"
  2.  
  3. QuickSort3::QuickSort3(int n, int* x) : QuickSort(n, x) {
  4. this->algName = "Quick Sort [Left] optimized";
  5. }
  6.  
  7. void QuickSort3::Run(void)
  8. {
  9. this->Launch(0, (this->n - 1));
  10. }
  11.  
  12. void QuickSort3::Launch(int l, int u) {
  13. if (l >= u)
  14. return;
  15.  
  16. int t, tmp;
  17. int i,j;
  18. t = this->x[l]; i = l; j = u+1;
  19.  
  20. while (1) {
  21. /* пропуск элементов справа и слева,
  22. чтобы не делать лишней работы */
  23. do i++; while (i <= u && this->x[i] < t);
  24. do j--; while (this->x[j] > t);
  25.  
  26. if (i > j)
  27. break;
  28. // Делаем swap(i, j):
  29. tmp = this->x[i]; this->x[i] = this->x[j]; this->x[j] = tmp;
  30. this->CountSwap();
  31. }
  32.  
  33. // swap(l, j)
  34. tmp = this->x[l]; this->x[l] = this->x[j]; this->x[j] = tmp;
  35. this->CountSwap();
  36.  
  37. this->Launch(l, j-1);
  38. this->Launch(j+1, u);
  39. }
  40.  
  41. QuickSort3::~QuickSort3(void)
  42. {
  43. }
  44.  
QuickSort3.cpp :: Реализация класса быстрой сортировки QSort3 [опорный элемент первый, пропуск одинаковых элементов]

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

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

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