Skip to content

Instantly share code, notes, and snippets.

@irchimi
Created June 24, 2020 20:15
Show Gist options
  • Save irchimi/7294a888e86b0fcd2a82af49d9cbeefb to your computer and use it in GitHub Desktop.
Save irchimi/7294a888e86b0fcd2a82af49d9cbeefb to your computer and use it in GitHub Desktop.
Quick Sort in C++
static void Swap(int& x, int& y) {
int swap = x;
x = y;
y = swap;
}
static int Partition(int arr[], int minIndex, int maxIndex) {
int pivot = arr[maxIndex];
int i = minIndex - 1;
for (int j = minIndex; j < maxIndex; j++) {
if (arr[j] < pivot) {
i++;
Swap(arr[i], arr[j]);
}
}
pivot++;
Swap(arr[i+1], arr[maxIndex]);
return i+1;
}
static void QuickSort(int arr[], int minIndex, int maxIndex) {
if (minIndex < maxIndex) {
int pivotIndex = Partition(arr, minIndex, maxIndex);
QuickSort(arr, minIndex, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, maxIndex);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment