Quick Sort

Partition method of sorting

What is quick sort?

Quick sort is a divide and conquer algorithm. It divides the large array into smaller sub-arrays. And then quick sort recursively sort the sub-arrays.

Why quick sort?

Quick sort reduces the space complexity and removes the use of the auxiliary array that is used in merge sort. Selecting a random pivot in an array results in an improved time complexity in most of the cases.

Quick sort : Breakdown in basic steps-

Step 1 : Choosing the pivot element

Choosing the pivot.

Pivot can be any element of the array.

Step 2 : Partition

We will rearrange the array elements in such a way that the all values lesser than the pivot should come before the pivot and all the values greater than the pivot should come after it.

What we achieve after each pass of the quick sort is that pivot element is placed at its correct location just how during the bubble sort after every pass the largest element is places at its correct location.

Let’s take example to understand this in better way,

[5 8 1 3 7 10 2] In this we will take 5 as pivot. After the first pass the array will become,

[1 3 2 ] 5 [8 7 10]

In the above array we can observe that the pivot element is at its correct location.

Step 3 : Recursive

Now to get the sorted array we perform the above steps recursively to all the sub-arrays and sort the elements.

The base case for the above recursive call would be as follows:

💡 If the array has zero or one element, there is no need to call the partition method. So we need to stop the recursive call when the array size is less than or equal to 1.

Placement of pivot element :

Now we have understood the working of the quick sort hence our next question will be how to choose the pivot element and once we have the pivot how do we put it at its correct location?

For putting the pivot at its correct location what we do is we take 2 pointers, one from the start and other from the end and we swap them if they are not in the correct sub-array like if the pivot is 5 and 10 is in the left sub-array, then it is not its correct position that is it is greater than pivot hence it should be in the right sub-array and is 1 is present in the right sub-array which is also not the correct position as it is less than the pivot element hence it should be in the left sub-array. When we find such 2 numbers then we swap them and eventually the pivot is at its correct location.

You can understand this very clearly through the following image, in this after one pass what happens is explained very well.

We can see how the pivot is placed at the correct position. Source

Quick Sort visualiser:

Now, we are going to see visualiser for quick sort it will help you to understand the working of the quick sort. In this visualiser they have taken last element as the pivot element. Now, go ahead and enjoy the visualiser.

Quicksort Visualization

#include<iostream>
#include<vector>

using std::cout,std::cin,std::endl;

int Partition (std::vector<int> &v, int low, int high)
{
    int pivot = v[low];
    int i = low;
    int j = high;
    do
    {
        do{i++;}while(pivot>=v[i]);
        do{j--;}while(pivot<v[j]);
        if(j>i)
        {
            std::swap(v[i],v[j]);
        }

    } while (i<j);
    std::swap(v[low],v[j]);  
    return j; 
}

void QuickSort(std::vector<int> &v, int low, int high)
{
    if(low<high)
    {
        int j = Partition(v,low,high);
        QuickSort(v,low,j);
        QuickSort(v,j+1,high);
    }
}

int main()
{
    std::vector <int> v = {-2,8,-2,9,0,-45,0,2,7,57,-3};

    QuickSort(v,0,v.size());

    for(auto value : v)
    {
        std::cout << value << " ";
    }

    return 0;
}

JAVA CODE:

public class Main
{
    static void quicksort(int arr[], int low, int high){
        if(low<high){
            int pi = partition(arr,low,high);
            
            quicksort(arr,low,pi-1);
            quicksort(arr,pi+1,high);
        }
    }
    
    static int partition(int arr[], int low, int high){
        int pivot = arr[high];
        int i = low-1;
        int j =0;
        
        for(j=low; j<high; j++){
            if(arr[j]<pivot){
                i++;
                
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        i++;
        int temp = arr[i];
        arr[i] = arr[high];
        arr[high] = temp;
        
        return i;
    }
 public static void main(String[] args) {
  int a[] = {5,4,3,2,1};
  Main o = new Main();
  o.quicksort(a,0,4);
  for(int i=0; i<a.length; i++){
      System.out.print(a[i] + " ");
  }
 }
}

Time & Space Complexity:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.