Quick sort is one of the efficient sorting that is based on splitting the array into the smaller ones.

Like merge sort, quick sort also uses divide and conquer approach to sort the element. It chooses the pivot element and partition the given array.

Time complexity of Quick sort is 0(n log n).

Example:

Pseudo Code of Quick Sort Algorithm:

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  

    for (j = low; j <= high- 1; j++)
    {
        // checking condition current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

How Partition Logic work ?

Input array : arr[] = {5, 75, 25, 85, 35, 45, 65}

  • low=0 and high =6 (array indexes), Pivot= 65 (last element)
  • j=0 , here arr[j] < pivot , i becomes 0 , no swapping occures as both i and j are 0.
  • j=1, here 75 > 65 do nothing .-> 5,75,25,85,35,45,65 .
  • j=2, here 25 < 65, i becomes 1 and swap 25 and 75 –> 5,25,75,85,35,45,65.
  • j=3, here 85 > 65 , do nothing –> 5,25,75,85,35,45,65 .
  • j=4, here 35 < 65 , i becomes 2 and swap 35 and 75 –> 5,25,35,85,75,45,65 .
  • j=5 here 45 < 65 , i becomes 3 and swap 85 and 45 –> 5,25,35,45,75,85,65.
  • Exit the loop.
  • Swap (i+1)=75 and arr[high]=65 –> 5,25,35,45,65,85,75
  • Break the array on 65 into two parts and sort them individually.

Implementation:

C

#include<stdio.h>  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 

int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        
        if (arr[j] < pivot) 
        { 
            i++;    
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  
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); 
    } 
} 
  

void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  

int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    quickSort(arr, 0, n-1); 
    printf("Sorted array: n"); 
    printArray(arr, n); 
    return 0; 
}

Java

public class QuickSortAlgorithm {


 public static void main(String[] args) {

int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSort(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}

public static int partition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}

int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSort(int[] array, int start, int end) {
if (start < end) {
int pivot = Partition(array, start, end);
quickSort(array, start, pivot - 1);
quickSort(array, pivot + 1, end);
}
}
}

Python

def partition(Array,low,up):
	i = low+1
	j = up
	pivot = Array[low]
	while(i<=j):
		while(Array[i]<pivot and i<up):
			i = i+1
		while(Array[j]>pivot):
			j = j-1
		if(i<j):
			Array[i],Array[j] = Array[j],Array[i]
			i = i+1
			j = j-1
		else:
			i = i+1
	Array[low] = Array[j]
	Array[j] = pivot
	return j
 
def quick(Array,low,up):
	if(low>=up):
		return
	piv_loc = partition(Array,low,up)
	quick(Array,low,piv_loc-1)
	quick(Array,piv_loc+1,up)
 
Array = [48,44,19,59,72,80,42,65,82,8,95,68]
low = 0
up = len(Array) - 1
quick(Array,low,up)
for a in array:
	print(a)

C++

#include <iostream> 
using namespace std;  
  

void swap(int* a, int* b)  
{  
    int t = *a;  
    *a = *b;  
    *b = t;  
}  
  

int partition (int arr[], int low, int high)  
{  
    int pivot = arr[high]; 
    int i = (low - 1);   
  
    for (int j = low; j <= high - 1; j++)  
    {  
          
        if (arr[j] < pivot)  
        {  
            i++;  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  
    return (i + 1);  
}  
  

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);  
    }  
}  

void printArray(int arr[], int size)  
{  
    int i;  
    for (i = 0; i < size; i++)  
        cout << arr[i] << " ";  
    cout << endl;  
}  
  
 
int main()  
{  
    int arr[] = {10, 7, 8, 9, 1, 5};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    quickSort(arr, 0, n - 1);  
    cout << "Sorted array: \n";  
    printArray(arr, n);  
    return 0;  
}  

Few Interview questions on Quick Sort:

Question: What is the best, average and worst case time complexity of quick sort ?

Answer:

  • Worst Case: O(n^2) .
  • Avegare Case: O(n log n)
  • Best Case: O(n log n)

Question: Why Quick Sort is preferred over MergeSort for sorting Arrays ?

Answer: Quick Sort in its general form is an in-place sort (i.e. it doesn’t require any extra storage) whereas merge sort requires O(N) extra storage, N denoting the array size which may be quite expensive.

Question: Is Pivot element always picked as the last element in the array ?

Answer: No , it can be any element from the array.

  • Pick first element as pivot.
  • Pick last element as pivot
  • Pick a random element as pivot.
  • Pick median as pivot.

That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉

Thanks Abhijeet Gupta for helping us to grow day by day. Abhijeet is expert in Data Structure and loves to solve competitive problems.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert