Код quicksort реализации приведен в листинге 1. Эта quicksort реализация использует основную стратегию выбора центра как выбор среднего элемента. Это простой подход к реализации, и иногда он может привести к проблемам эффективности, когда алгоритм выбирает или самое маленькое или самое большое значение в качестве центра. В этих случаях производительность алгоритма ухудшается в два раза, так как алгоритм quicksort может рекурсивно разделить только один подмассив вместо двух.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: | template <typename T>void quick_sort(vector<T>& v, int low, int high) { // Do not solve recursively when faced with // only 1 or 2 elements if (low == high) { return ; } else if (low + 1 == high) { if (v[low] > v[high]) { swap(v[low], v[high]); return ; } } // select pivot int middle = (low + high) / 2; T pivot = v[middle]; swap(v[middle], v[high]); // partition int i; int j; for (i = low, j = high - 1; ;) { while (v[i] < pivot && i < j) i++; while (pivot < v[j] && i < j) j--; if (i < j) { swap(v[i], v[j]); } else { break; } } // place pivot in correct location if (i != high - 1 && j != high - 1) { swap( v[i], v[high]); } // quicksort sub-vectors if (i == low && j == low) { quick_sort(v, low + 1, high); } else if (i == high - 1 && j == high - 1) { quick_sort(v, low, high - 1); } else { quick_sort(v, low, i - 1); quick_sort(v, i + 1, high); } } |
| Listing 1 A Quicksort implementation |
Более усовершенствованная quicksort реализация приведена в учебнике Вайс на странице 347. Реализация Вайса использует свою стратегию разделения и получения центра, известную как median-of-three partitioning. Эта оптимизированная стратегия улучшает производительность quicksort, препятствуя алгоритму выбрать минимальное или максимальное значение как центр. Эта реализация также определяет минимальный размер массива, на котором будет рекурсивно работать алгоритм. Когда обработана часть массива, который меньше чем размер сокращения, Вайс quicksort выполняет вид вставки.