Quick Sort

Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

Given an array arr[], its starting position low and its ending position high.

Implement the partition() and quickSort() functions to sort the array.

• Time : O(nlogn) | worst O(n^2)
• Space : O(1)

class Solution {
public:
    //Function to sort an array using quick sort algorithm.
    void quickSort(int arr[], int low, int high) {
        if(low >= high) return;
        int m = partition(arr, low, high);
        quickSort(arr, low, m - 1);
        quickSort(arr, m + 1, high);
    }

public:
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int l = low, r = high - 1;
        while(l <= r) {
            while(l <= r and arr[l] <= pivot) l++;
            while(l <= r and arr[r] >= pivot) r--;
            if(l <= r and arr[l] >= arr[r]) swap(arr[l++],arr[r--]);
        }
        swap(arr[l], arr[high]);
        return l;
    }