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

Выполнен в стиле ООП: каждый тип сортировки - класс производный от единого родительского абстрактного класса Sort.
В каждом таком классе - искомый алгоритм сортировки инкапсулируется в методе Run().

На вход подаются массивы различной заданной размерности, и в разных вариантах: полностью случайные числа и частично отсортированные последовательности. RandomGenerator - класс формирования этих массивов: RandomGenerator.h, RandomGenerator.cpp.

Время оценивается счетчиками с точностью до микросекунд, работающими через QueryPerformance. В данном примере используется этот: Timer.h, Timer.cpp
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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