quick sort c++

Sure! Here's an implementation of the Quick Sort algorithm in C++:

#include <iostream>
#include <vector>

// Function to partition the array and return the pivot index
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Function to perform quick sort recursively
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    std::vector<int> arr = {9, 5, 2, 7, 1, 8};
    
    std::cout << "Array before sorting: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    quickSort(arr, 0, arr.size() - 1);
    
    std::cout << "\nArray after sorting: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    return 0;
}

In this example, the `partition` function is used to choose a pivot element from the array and rearrange the elements such that all elements less than or equal to the pivot are on the left side, and all elements greater than the pivot are on the right side. The function returns the index of the pivot element.

The `quickSort` function is a recursive function that repeatedly partitions the array and sorts the sub-arrays on either side of the pivot.

The main function demonstrates the usage of the Quick Sort algorithm by creating a vector of integers, sorting it using `quickSort`, and then printing the sorted array.

Note that this implementation uses the last element as the pivot. There are other variations of the Quick Sort algorithm that use different pivot selection strategies.