Quick Sort

Introduction

Quick Sort is a popular divide-and-conquer algorithm used to sort elements in a list or array. It works by picking one element as a pivot and then rearranging the rest of the elements so that:

Elements less than the pivot go to the left, and
Elements greater than the pivot go to the right.

This process is called partitioning. After that, the same steps are recursively applied to the left and right parts until the whole list is sorted.

How Quick Sort Works?

Choose a pivot (can be the first, last, middle, or random element).

Partition the array so that:

Elements less than the pivot go to the left.
Elements greater than the pivot go to the right.

Recursively apply the above steps to the sub-arrays (left and right of the pivot).

Combine the sorted sub-arrays and the array is now sorted.

Implementation of Quick Sort

// quicksort.cpp
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int> &v, int low, int high)
{
int par = low;
for (int i = low; i < high; i++)
{
    if (v[i] <= v[high])
    {
        swap(v[i], v[par]);
        par++;
    }
}
swap(v[par], v[high]);
return par;
}
void quickSort(vector<int> &v, int low, int high)
{
if (low >= high)
    return;
int pi = partition(v, low, high);
quickSort(v, low, pi - 1);
quickSort(v, pi + 1, high);
}
int main()
{
vector<int> v{8, 3, 2, 7, 9, 4, 5};
quickSort(v, 0, v.size() - 1);
for (int &ele : v)
{
    cout << ele << " ";
}
}

#quicksort.py
def partition(arr,low,high):
     par=low
     for i in range(low,high):
         if(arr[i]<=arr[high]):
             (arr[i],arr[par])=(arr[par],arr[i])
             par=par+1
     
     arr[par],arr[high]=arr[high],arr[par]
     return par
def quickSort(arr,low,high):
     if(low>=high):
         return
     pi=partition(arr,low,high)
     quickSort(arr,low,pi-1)
     quickSort(arr,pi+1,high)

arr=[8, 3, 2, 7, 9, 4, 5]
quickSort(arr,0,len(arr)-1)
for ele in arr:
 print(ele)

console.log("We're Working");

Time Complexity

Best Case: When the pivot always splits the array into two equal halves.
- Each level of recursion divides the array evenly, resulting in log(n) levels.
- Time Complexity : O(n log n)
Average Case: When the pivot divides the array into reasonably balanced parts.
- Typical for randomly ordered data.
- Time Complexity : O(n log n)
Best Case: When the pivot is always the smallest or largest element (e.g. sorted or reverse sorted array with poor pivot selection).
- Leads to highly unbalanced partitions.
- Time Complexity : O(n^2)

Space Complexity

Quick Sort is usually implemented using recursion.Though it sorts in place, it uses stack space for recursive calls.
Space Complexity : O(n)