Quick Sort

Implementation from [1]

// C++ implementation of QuickSort 
#include <bits/stdc++.h> 
using namespace std;
// A utility function to swap two elements 
void swap(int* a, int* b) { 
    int t = *a; 
    *a = *b; 
    *b = t; 
}
// This function takes last element as pivot, places 
// the pivot element at its correct position in sorted 
// array, and places all smaller (smaller than pivot) 
// to left of pivot and all greater elements to right 
// of pivot 
int partition (int arr[], int low, int high) { 
    int pivot = arr[high];  
    int i = (low - 1); // Index of smaller element 
    
    for (int j = low; j <= high - 1; j++) { 
        // If current element is smaller than the pivot 
        if (arr[j] < pivot) { 
            i++; 
            swap(&arr[i], &arr[j]);
        }
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}
// The main function that implements QuickSort 
// arr[] --> Array to be sorted, 
// low --> Starting index, 
// high --> Ending index 
void quickSort(int arr[], int low, int high) {
    if (low < high) { 
        // pi is partitioning index, arr[p] is now 
        // at right place 
        int pi = partition(arr, low, high); 
        
        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
}
// Function to print an array
void printArray(int arr[], int size) { 
    int i; 
    for (i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
}
// Driver Code 
int main() { 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    quickSort(arr, 0, n - 1); 
    cout << "Sorted array: \n"; 
    printArray(arr, n); 
    return 0; 
}
// This code is contributed by rathbhupendra

My own implementation

#include <iostream>
#include <vector>
using namespace std;
void quicksort(vector<int>& a, int i, int j) {
    if (i >= j || i < 0 || j >= a.size()) return;
    // pick up the first element as pivot
    int pivot = a[i], pivot_idx = i + 1;
    for (int k = i + 1; k <= j; ++k) {
        if (a[k] <= pivot) {
            swap(a[k], a[pivot_idx++]);
        }
    }
    pivot_idx--;
    swap(a[i], a[pivot_idx]);
    quicksort(a, i, pivot_idx - 1);
    quicksort(a, pivot_idx + 1, j);    
}
int main() {
    vector<int> a = {10, 6, 7, 8, 9, 0, 6};
    cout << "Before sorting:" << endl;
    for (auto x : a) cout << x <<" ";
    cout << endl;
    quicksort(a, 0, a.size() - 1);
    cout << "After sorting:" << endl;
    for (auto x : a) cout << x <<" ";
    cout << endl;
    
}

Reference

[1] https://www.geeksforgeeks.org/quick-sort/