A quicksort implementation appears in Listing 1. This quicksort implementation uses a basic pivot selection strategy of selecting the middle element. This is a simple approach to implement, but one that can lead to efficiency problems when the algorithm selects either the smallest or largest value as the pivot. In these cases, the performance of the algorithm degrades since the algorithm can only recursively quicksort one sub-array instead of two.
| 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 |
A more advanced quicksort implementation appears on page 347 of the Weiss textbook. The Weiss implementation uses a different pivot and partition strategy known as median-of-three partitioning. This optimized strategy improves quicksort's performance by preventing the algorithm from selecting the minimum or maximum value as the pivot. This implementation also specifies a minimum array size that the algorithm will recursively operate on. When presented with a portion of an array that is smaller than this cut-off size, the Weiss quicksort implementation performs an insertion sort.