Quick Sort

Quick sort is an algorithm of the divide and conquer type. That is,the problem of sorting a set is reduced of the problem of sorting two smaller sets.

How it works?

Quick sort works in the following way –

Choose an item from array called as pivot
Move all the elements smaller than pivot to left partition
Move all the elements greater than pivot to right partition.

Choose new pivot item in each partition and keep doing the same process again until partition of one element each aren’t formed.

How to choose Pivot?

First element as pivot.
Last element as pivot (We use this in our examples & Code)
Random element as pivot.
Median element as pivot.

Execution of quick sort

Quicksort works recursively, Partitioning moves all smaller elements to the left of the pivot and greater to the right side of the pivot, thus each time two sub-array partitions are formed. Thus again, we do partitioning in each of these sub-arrays individually.

Following code below gives a perfect example for this –

QuickSort Algorithm

  
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* indexPI is partitioning index, partition() function will 
        return index of partition */
        indexPI = partition(arr, low, high);

        quickSort(arr, low, indexPI - 1);  // left partition
        quickSort(arr, indexPI + 1, high); // right partition
    }
}

Partition Algorithm

  
partition (arr[], low, high)
{
    // pivot element selected as right most element in array each time
    pivot = arr[high];  

    swapIndex = (low - 1)  //swapping index

    for (j = low; j <= high- 1; j++)
    {
        // Check if current element is smaller than pivot element
        if (arr[j] < pivot)
        {
            i++;    // increment swapping index
            swap arr[j] and arr[swapIndex]
        }
    }
    swap arr[swapIndex + 1] and arr[high])
    return (swapIndex + 1)
}

Quick Sort Algorithm

Quick Sort Partioning

Code

  
#include<stdio.h>

  
// A utility function to swap two elements 
void swap(int* x, int* y) 
{ 
    int temp = *x; 
    *x = *y; 
    *y = temp; 
} 
  
/* Partition function to do Partition
elements on the left side of pivot elements would be smaller than pivot
elements on the right side of pivot would be greater than the pivot
*/
int partition (int array[], int low, int high) 
{ 
    // pivot element selected as right most element in array each time
    int pivot = array[high];    
    int swapIndex  = (low - 1);   //swapping index
  
    for (int j = low; j <= high- 1; j++) 
    { 
        // Check if current element is smaller than pivot element
        if (array[j] < pivot) 
        { 
            swapIndex ++;    // increment swapping index
            swap(&array[swapIndex], &array[j]); 
        } 
    } 
    swap(&array[swapIndex + 1], &array[high]); 
    return (swapIndex + 1); 
} 
  
//Recursive function to apply quickSort
void quickSort(int array[], int low, int high) 
{ 
    if (low < high) 
    { 
       /* indexPI is partitioning index, partition() function will 
        return index of partition */
        int indexPI  = partition(array, low, high); 
  
        quickSort(array, low, indexPI  - 1);  // left partition
        quickSort(array, indexPI  + 1, high); // right partition
    } 
} 
  
/* Function to display the array */
void display(int array[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", array[i]); 
} 
  
//Main function to run the program
int main() 
{ 
    int array[] = {70, 90, 10, 30, 50, 20, 60};
    
    int size = sizeof(array)/sizeof(array[0]);
    printf("Array before Quick Sorting: ");
    display(array,size);
     
    quickSort(array, 0, size-1); 
    printf("\nArray after Quick Sorting: "); 
    display(array, size); 
    return 0; 
}

  
#include<iostream>
using namespace std;

//Function to swap two elements. 
void swap(int* x, int* y) 
{ 
    int temp = *x; 
    *x = *y; 
    *y = temp; 
} 
  
/* Partition function to do Partition
elements on the left side of pivot elements would be smaller than pivot
elements on the right side of pivot would be greater than the pivot
*/
int partition (int array[], int low, int high) 
{ 
    //Pivot element selected as right most element in array each time.
    int pivot = array[high];    
    int swapIndex  = (low - 1);   //swapping index.
  
    for (int j = low; j <= high- 1; j++) 
    { 
        //Check if current element is smaller than pivot element.
        if (array[j] < pivot) 
        { 
            swapIndex ++;    //increment swapping index.
            swap(&array[swapIndex], &array[j]); 
        } 
    } 
    swap(&array[swapIndex + 1], &array[high]); 
    return (swapIndex + 1); 
} 
  
//Recursive function to apply quickSort
void quickSort(int array[], int low, int high) 
{ 
    if (low < high) 
    { 
       /* indexPI is partitioning index, partition() function will 
        return index of partition */
        int indexPI  = partition(array, low, high); 
  
        quickSort(array, low, indexPI  - 1);  //left partition
        quickSort(array, indexPI  + 1, high); //right partition
    } 
} 
  
//Function to display the array
void display(int array[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        cout<< array[i] <<" "; 
} 
  
//Main function to run the program
int main() 
{ 
    int array[] = {70, 90, 10, 30, 50, 20, 60}; 
    int size = sizeof(array)/sizeof(array[0]);
    
    cout<< "Array before Quick Sorting: "; 
    display(array, size); 
    
    
    quickSort(array, 0, size-1); 
    
    cout<< "\nArray after Quick Sorting: "; 
    display(array, size); 
    
    return 0; 
}

  

      
  
//Java Program for Merge Sort
class Main {
    // this function display the array
    public static void display(int[] arr, int size)
    {
        for(int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    // main function of the program
    public static void main(String[] args)
    {
        int[] a = {70, 90, 10, 30, 50, 20, 60};

        int size = a.length;
        
        System.out.print("Array before Quick Sorting: ");
        display(a, size);

        quickSort(a, 0, size - 1);
        
        System.out.print("Array after Quick Sorting: ");
        display(a, size);
    }
    // A utility function to swap two elements
    static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //Recursive function to apply quickSort
    static void quickSort(int[] arr, int low, int high)
    {
        if (low < high)
        {
       /* indexPI is partitioning index, partition() function will
        return index of partition */
            int indexPI  = partition(arr, low, high);

            quickSort(arr, low, indexPI  - 1);  //left partition
            quickSort(arr, indexPI  + 1, high); //right partition
        }
    }
    /* Partition function to do Partition
    elements on the left side of pivot elements would be smaller than pivot
    elements on the right side of pivot would be greater than the pivot
    */
    static int partition(int[] arr, int low, int high)
    {
        // Pivot element selected as right most element in array each time.
        int pivot = arr[high];
        int swapIndex  = (low - 1);   //swapping index.

        for (int j = low; j <= high- 1; j++)
        {
            //Check if current element is smaller than pivot element.
            if (arr[j] < pivot)
            {
                swapIndex++;    //increment swapping index.
                swap(arr, swapIndex, j);
            }
        }
        // swap swapindex+ 1 and pivot index
        // we assigned pivot = arr[high] is pivot index is high
        swap(arr, swapIndex + 1, high);

        return (swapIndex + 1);
    }
}

	
Array before Quick Sorting: 70 90 10 30 50 20 60 
Array after Quick Sorting: 10 20 30 50 60 70 90

Facts about Quick Sort

Quicksort is an in-place algorithm. In-place sorting means, it does not use additional storage space to perform sorting.
The algorithm is efficient for large-sized data sets.
The average or best-case complexity of quicksort is O(n log n).
Worst-case time complexity is O(n^2)
Cache Friendly: Quick Sort is also a cache-friendly sorting algorithm as it has a good locality of reference when used for arrays

Time Complexity for Quick Sort

Time complexity	Best	Worst	Space Complexity	Auxiliary Space Complexity
O(n log n)	O(n log n)	O(n²)	O(1)	O(log n)

→

←

Courses

Chapters

Aptitude

Sorting

Linked List

Stack

Queue

Tree

Quick Sort

Quick Sort