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

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

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

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