Задача: Сравнение алгоритмов быстрой сортировки
Исходник: Анализ быстрых сортировок массива, язык: C++ [code #51, hits: 7560]
автор: this [добавлен: 18.02.2006]
  1. #include "Insert.h";
  2. #include "QuickSort.h";
  3. #include "QuickSortLeft.h";
  4. #include "QuickSort3.h";
  5. #include "QuickSort4.h";
  6.  
  7. #include "Timer.h";
  8. #include "RandomGenerator.h";
  9.  
  10. int main()
  11. {
  12. srand( (unsigned)time(NULL));
  13.  
  14. // Начальный массив, нужен лишь для инициализации
  15. int* _x;
  16.  
  17. // Количество размерностей массивов
  18. const int sizeNum = 5;
  19. int sizes[sizeNum] = {4000, 8000, 10000, 15000, 20000};
  20.  
  21. // Количество видов сортировок
  22. const int sortTypeNum = 4;
  23.  
  24. // Инициируем различные виды быстрой сортировки
  25. QuickSort QSortCenterObj(0, _x);
  26. QuickSortLeft QSortLeftObj(0, _x);
  27. QuickSort3 QSort3Obj(0, _x);
  28. QuickSort4 QSort4Obj(0, _x, 10);
  29.  
  30.  
  31. // Им будем подсчитывать время
  32. Timer timerObj(sortTypeNum);
  33.  
  34. Sort* sorts[sortTypeNum];
  35. sorts[0] =& QSortCenterObj;
  36. sorts[1] =& QSortLeftObj;
  37. sorts[2] =& QSort3Obj;
  38. sorts[3] =& QSort4Obj;
  39.  
  40. // Цикл по 2 режимам состава массивов:
  41. // случайные / частично-отсортированные числа
  42. for (int k = 0; k < 2; k++) {
  43. if (0 == k) cout << "I. Random Numbers";
  44. else cout << "II. PARTLY Random Numbers";
  45. cout << endl;
  46.  
  47. // Цикл по размерам массива
  48. for (int i = 0; i < sizeNum; i++) {
  49. cout << " " << i + 1 << ") Array Size(N): " << sizes[i] << "\n";
  50.  
  51. // ... по видам сортировок
  52. for (int j = 0; j < sortTypeNum; j++) {
  53. int N = sizes[i];
  54. int* x = new int[N];
  55. RandomGenerator genObj(N);
  56.  
  57. // В зависимости от режима - заполняем исходный массив
  58. if (0 == k) x = genObj.GetRandom(0, 100);
  59. else x = genObj.GetPartSorted(N/10, N/5);
  60.  
  61. // Уточняем размер и передаем исходный сформированный массив
  62. sorts[j]->setSize(N);
  63. sorts[j]->setArr(x);
  64.  
  65. // Засекаем время
  66. timerObj.Start(0);
  67. sorts[j]->Run(); // Прогоняем сортировку текущего вида
  68. float exTime = timerObj.Get(0, 1); // Фиксируем время
  69.  
  70. // Выводим время выполнения и количество перестановок
  71. cout.setf(ios::fixed | ios::showpoint);
  72. cout << " " << exTime << " sec.:: ";
  73. cout.width(8);
  74. cout << sorts[j]->getSwapNum() << " swaps :: " << sorts[j]->getName() << "\n";
  75.  
  76. delete [] x;
  77. }
  78. cout << "\n";
  79. }
  80. cout << "\n\n";
  81. }
  82.  
  83. return 0;
  84. }
На вход подаются массивы с количеством элементов: 4000 - 20000.
В 2-х режимах: полностью случайные и частично отсортированные.

Файлы: Insert.h, Insert.cpp, QuickSort.h, QuickSort.cpp, Timer.h, Timer.cpp, RandomGenerator.h, RandomGenerator.cpp
(остальные - перечислены в задаче)

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

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