Quicksort in C++
Below is an example of the Quicksort algorithm in C++. See the Quicksort page for more information and implementations.
quicksort in C++
#include <vector>
#include <iostream>
static int partition(std::vector<int> &arr, int startIndex, int endIndex) {
int pivotIndex = (startIndex + endIndex) / 2;
int pivotValue = arr[pivotIndex];
while (true) {
// start at the FIRST index of the sub-arr and increment
// FORWARD until we find a value that is > pivotValue
while (arr[startIndex] < pivotValue) {
startIndex++;
}
// start at the LAST index of the sub-arr and increment
// BACKWARD until we find a value that is < pivotValue
while (arr[endIndex] > pivotValue) {
endIndex--;
}
if (startIndex >= endIndex) {
return endIndex;
}
// swap values at the startIndex and endIndex
int temp = arr[startIndex];
arr[startIndex] = arr[endIndex];
arr[endIndex] = temp;
}
}
void quickSort(std::vector<int> &arr, int startIndex, int endIndex) {
// verify that the start and end index have not overlapped
if (startIndex < endIndex) {
// calculate the pivotIndex
int pivotIndex = partition(arr, startIndex, endIndex);
// sort the left sub-arr
quickSort(arr, startIndex, pivotIndex);
// sort the right sub-arr
quickSort(arr, pivotIndex + 1, endIndex);
}
}
int main() {
std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
quickSort(arr, 0, static_cast<int>(arr.size() - 1));
for (int i; i < arr.size(); i++) {
std::cout << arr[i];
if (i < arr.size() - 1) std::cout << ", ";
}
}