Skip to content

Instantly share code, notes, and snippets.

@piusayowale
Created January 24, 2022 11:04
Show Gist options
  • Save piusayowale/e74f7604d4ea3ca25b4d694ac01dc76f to your computer and use it in GitHub Desktop.
Save piusayowale/e74f7604d4ea3ca25b4d694ac01dc76f to your computer and use it in GitHub Desktop.
Quick sort in cpp
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int* arr, int low, int hi) {
int pivot = arr[hi];
int tempIdx = low - 1;
for (int i = low; i < hi- 1; i++) {
if (arr[i] <= pivot) {
tempIdx = tempIdx + 1;
swap(&arr[tempIdx], &arr[i]);
}
}
swap(&arr[tempIdx + 1], &arr[hi]);
return tempIdx + 1;
}
void quickSort(int* arr, int low, int hi) {
if (low >= hi || low < 0) {
return;
}
int p = partition(arr, low, hi);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, hi);
}
int main() {
int arr[] = { 5, 7, 2, 3, 0, 9, -1 };
quickSort(arr, 0, 6);
for (int i = 0; i < 7; i++) {
std::cout << arr[i] << " ";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment