QuickSort_GL
  1. What is Quick Sort
  2. Quick Sort Pseudocode
  3. Quick Sort Algorithm
  4. Quick Sort Time Complexity
  5. Quick Sort Space Complexity
  6. Quick Sort in C
  7. Quick Sort in Java
  8. Quick Sort in C++
  9. Quick Sort in Python
  10. Quick Sort Example
  11. Difference between Quick Sort and Merge Sort

What is Quick Sort

Quick sort algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm. We usually use Recursion in quicksort implementation. In each recursive call, a pivot is chosen, then the array is partitioned in such a way that all the elements less than pivot lie to the left and all the elements greater than pivot lie to the right.

After every call, the chosen pivot occupies its correct position in the array which it is supposed to as in a sorted array. So with each step, our problem gets reduced by 2 which leads to quick sorting. Pivot can be an element. Example: last element of the current array or the first element of current array or random pivot etc.

quick sort

Quick Sort Pseudocode

  • We are given with an input array
  • Choose pivot, here we are choosing the last element as our pivot
  • Now partition the array as per pivot
    • Keep a partitioned index say p and initialize it to -1
    • Iterate through every element in the array except the pivot
    • If an element is less than the pivot element then increment p and swap the elements at index p with the element at index i.
    • Once all the elements are traversed, swap pivot with element present at p+1 as this will the same position as in the sorted array
    • Now return the pivot index
  • Once partitioned, now make 2 calls on quicksort
    • One from beg to p-1
    • Other from p+1 to n-1

Quick Sort Algorithm

quickSort(arr, beg, end)
  if (beg < end)
    pivotIndex = partition(arr,beg, end)
    quickSort(arr, beg, pivotIndex)
    quickSort(arr, pivotIndex + 1, end)

partition(arr, beg, end)
  set end as pivotIndex
  pIndex = beg - 1
  for i = beg to end-1
  if arr[i] < pivot
    swap arr[i] and arr[pIndex]
    pIndex++
  swap pivot and arr[pIndex+1]
return pIndex + 1

Quick Sort Time Complexity

  • Partition of elements take n time
  • And in quicksort problem is divide by the factor 2
  • Best Time Complexity : O(nlogn)
  • Average Time Complexity : O(nlogn)
  • Worst Time Complexity : O(n^2)
  • Worst Case will happen when array is sorted

Quick Sort Space Complexity

  • O(n) : basic approach
  • O(logn) : modified approach

Learn about Bubble sort

Quick Sort in C

#include<stdio.h> 

// Function to swap the elements 
void swap_elements(int* first, int* second) 
{ 
	int temp = *first; 
	*first = *second; 
	*second = temp; 
} 

// In partition function l represents low and h represents high
int partition_function(int arr[], int l, int h) 
{ 
	int p = arr[h]; // pivot is the last element
	int i = (l - 1); // Index of smaller element 

	for (int j = l; j <= h- 1; j++) 
	{ 
		// If current element is smaller than the pivot 
		if (arr[j] < p) 
		{ 
			i++; 
			swap_elements(&arr[i], &arr[j]); // swapping the elements
		} 
	} 
	swap_elements(&arr[i + 1], &arr[h]); 
	return (i + 1);   
} 

void quick_sort(int arr[], int l, int h) 
{ 
	if (l < h) 
	{ 
		int p_index = partition_function(arr, l, h); 
		quick_sort(arr, l, p_index - 1); 
		quick_sort(arr, p_index + 1, h); 
	} 
} 

//Function to print the elements of the array 
void print_Array(int arr[], int len) 
{ 
	int i; 
	for (i=0; i < len; i++) 
		printf("%d ", arr[i]);  
} 

// Main Function or driver function
int main() 
{ 
	int array[] = {14, 17, 8, 90, 11, 2}; //Static array
	int length = sizeof(array)/sizeof(array[0]); //For finding the length of the array
	printf("Before Sorting the array: ");
	print_Array(array, length);
	printf("\n");
	printf("After Sorting the array: ");
       //Indexing starts from 0(zero) in array (that is why length-1)
        quick_sort(array, 0, length-1); 
	print_Array(array, length); 
	return 0; 
} 

Output of the program:

Before Sorting the array: 14 17 8 90 11 2 
After Sorting the array: 2 8 11 14 17 90 

QuickSort in Java

import java.util.*;
public class QuickSortDemo
{
    static void quickSort(int[] a,int p,int r) 
	{
		if(p<r)
		   {int q=partition(a,p,r);
			quickSort(a,p,q-1);
			quickSort(a,q+1,r);
	
		   }
		 
	}
	
	static int partition(int[] a,int b,int r)  // partition method 
	{
		int pivot=a[r];
		int pindex=b-1;
		for(int i=b;i<r;i++)
		{
			if(a[i]<=pivot)
			{
				pindex++;
				int t=a[i];
				a[i]=a[pindex];
				a[pindex]=t;
			}
		}
		pindex++;
		int t=a[pindex];
		a[pindex]=a[r];
		a[r]=t;
		return pindex;
		
	}
	
	static void display(int[] a)  // method to display the array
	{
		for(int i=0;i<a.length;i++)
			System.out.println(a[i]+" ");
	}
		
		
    
	public static void main(String[] args) // main method 
	{
		Scanner in=new Scanner(System.in);
		System.out.println(“enter size of array”);
                int n=in.nextInt();
		int[] a =new int[n];
		
                System.out.println(“enter the elements of array”);
		for(int i=0;i<a.length;i++)
		   a[i]=in.nextInt();
                quickSort(a,0,n-1);
                System.out.println(“Array after sorting the elements: ”);
                display(a);
	}
}

Output of the program:

Output of the program:
enter size of array
5
enter the elements of array
12
43
21
69
56
Array after sorting the elements:
12
21
43
56
69

Quick Sort in C++

#include <bits/stdc++.h> 
using namespace std;  

void swap(int* ele1, int* ele2)  // swapping the elements
{  
    int t = *ele1;  
    *ele1 = *ele2;  
    *ele2 = t;  
}  
  

int partition (int a[], int beg, int end)   // partitioning the elements
{  
    int pivot = a[end]; 
    int i = (beg - 1); 
  
    for (int j = beg; j <= end - 1; j++)  
    {  
      
        if (a[j] < pivot)  
        {  
            i++; 
            swap(&a[i], &a[j]);  
        }  
    }  
    swap(&a[i + 1], &a[end]);  
    return (i + 1);  
}  
  

void quickSort(int a[], int beg, int end)  // sorting the elements based on partitioning index
{  
    if (beg < end)  
    {  
        
        int pIndex = partition(a, beg, end);  
  
        quickSort(a, beg, pIndex - 1);  
        quickSort(a, pIndex + 1, end);  
    }  
}  
  
void display(int a[], int n)   // displaying the elements of the array
{  
  
    for (int i = 0; i < n; i++)  
        cout << a[i] << " ";  
    cout << endl;  
}  
  
int main()  
{  
    int a[] = {10, 7, 8, 9, 1, 5};  
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Elements of array before sorting: \n";  
    display(a, n);
    quickSort(a, 0, n - 1);  
    cout << "Elements of array after sorting: \n";  
    display(a, n);  
    return 0;  
}  
  


Output of the program:

Elements of array before sorting:
10 7 8 9 1 5 
Elements of array after sorting:
1 5 7 8 9 10 

Quick Sort in Python

def partition(array,l,h): 
    i = ( l-1 )          
    p = array[h]     
  
    for j in range(l, h): 
  
        
        if   array[j] < p: 
    
            i = i+1 
            array[i],array[j] = array[j],array[i] 
  
    array[i+1],array[h] = array[h],array[i+1] 
    return ( i+1 ) 
  
 
def quickSort(a,l,h): 
    if l < h: 
   
        pin = partition(a,l,h)        
        quickSort(a, l, pin-1) 
        quickSort(a, pin+1, h) 
  
 
arr = [100, 76, 80, 9, 111, 50] 
n = len(arr)-1 
quickSort(arr,0,n) 
print ("Elements of array after applying sorting:") 
for i in range(n): 
    print ("%d" %arr[i]), 




Output of the program:

Elements of array after applying sorting: 9 50 76 80 100 111

Learn about Bubble sort

Quick Sort Example

Example1:

Rearrange the array elements so that positive and negative numbers are placed alternatively. The relative ordering of elements do not matter

Example:

Input: [-1, 2, -3, 4, 5, 6, -7, 8, 9]

Output: [4, -3, 5, -1, 6, -7, 2, 8, 9]

Optimal Approach

  1. Follow quicksort approach by taking 0 as Pivot
  2. Partition the array around a pivot
  3. Now we will be having negative elements on the left-hand side and positive elements on the right-hand side.
  4. Take 2 index variable, neg=0 and pos=partition index+1
  5. Increment neg by 2 and pos by 1, and swap the elements
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Code of the above example:

import java.util.*;
class Main{
	public static void main (String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int arr[] = new int[n];
		for(int i=0;i<n;i++)
		    arr[i]=in.nextInt();
		rearrange(arr,n);
		for(int i=0;i<n;i++)
		    System.out.println(arr[i]);
	}
	
    static void rearrange(int arr[], int n) 
    { 
        int i = -1, tmp = 0; 
        for (int j = 0; j < n; j++) 
        { 
            if (arr[j] < 0) 
            { 
                i++; 
				tmp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = tmp; 
            } 
        } 

        int pos = i+1, neg = 0; 
        while (pos < n && neg < pos && arr[neg] < 0) 
        { 
            tmp = arr[neg]; 
            arr[neg] = arr[pos]; 
            arr[pos] = tmp; 
            pos++; 
            neg += 2; 
        } 
    } 

}

Example 2:

Move all 0’s to the end of the array while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]

Output: [1,3,12,0,0]

Optimal Approach:

  1. Take a partitioned index p = -1 and traverse all the elements 
  2. If they are not equal to 0, then increment p and swap elements at i and p index.

Code of the above example:

import java.util.*;
 
class Main{
	public static void main (String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int arr[] = new int[n];
		for(int i=0;i<n;i++)
		    arr[i]=in.nextInt();
		rearrange(arr,n);
		for(int i=0;i<n;i++)
		    System.out.println(arr[i]);
	}
	
    static void rearrange(int arr[], int n) 
    { 
         if(arr==null || n==0)
                return;
        int p=-1;       
        for(int i=0;i<n;i++){
            if(arr[i]!=0)
            {
                p++;
                int t=arr[i];
                arr[i]=arr[p];
                arr[p]=t;
            }
        }
        
    } 
 
}

Example 3:

Find the kth largest element in the given array. 

Example 1:

Input: [3,2,1,5,6,4] and k = 2

Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4

Output: 4

Note:

You may assume k is always valid, 1 ≤ k ≤ array’s length.

Optimal Approach:

  • Quicksort can be used to solve this problem
  • so if you want 4th largest in 9 size array then in sorted order it should be at 9-4+1 (i.e, n-k+1)
  • so start setting pivot one by one …as soon as pivot comes at n-k+1 position return
  • TC: linear in avg case with O(1) space

Code of the above example:

public int findKthLargest(int[] nums, int k) {
        int desired=nums.length-k;
        return quick(nums,desired,0,nums.length-1);
        
    }
    
    int quick(int[] nums,int desired,int start,int end){
       int p=partition(nums,start,end);
       if(p==desired)
            return nums[p];
        
        //depending on desired index we will move our quicksort
       if(desired<p)
           return quick(nums,desired,start,p-1);
        else
          // if(p<nums.length-1)
               return quick(nums,desired,p+1,end); 
       // return -1;
    }
    
    int partition(int[] a,int start,int end)
    {
        int i=start;
        int j=start;
        int piv=end;
        while(j<end)
        {
            if(a[j]<=a[piv])
            {
                int t=a[i];
                a[i]=a[j];
                a[j]=t;
                i++;
            }
            j++;
        }
     
      int t=a[i];
      a[i]=a[piv];
      a[piv]=t;
      return i;
        
    }

Difference between Quick Sort and Merge Sort

  • In terms of algorithm and complexity
    • In Quicksort, the partition of the array in the next iteration completely depends on the choice of the pivot element. We will have 2 arrays after placing the pivot to its correct position. So if we have a sorted array, the pivot will remain at the same position, leading to n^2 complexity, as no real partition will take place.
    • In Mergesort, we take the mid index which is (beg index + end index)/2. Our array will always break into two subsequent arrays with approximately equal length. This keeps the complexity to nlogn and is much time-efficient
  • In terms of space complexity
    • If we are implementing our sort algorithm using recursion, then obviously our recursion stack will take n space.
    • But in merge sort in every iteration we create two new temporary arrays. In one we copy all the left subarray and in other we copy all the right subarray. Since all the elements are copied, it takes another n space.
    • In quicksort no such temporary array creation and copying takes place. Therefore no extra n space is needed
  • In terms of speed
    • Quicksort is faster than merge sort because of the previous explanation.
    • No temporary array, copying etc happens in quicksort, making it much faster in execution
  • In terms of in-place
    • In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
    • Quicksort is in-place but merge sort is not as it needs extra n space for creating temporary arrays whose sixes adds up to n  
  • In terms of stability
    • Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
    • In quicksort, a lot of swapping takes place leading it to lose its stability whereas merge sort maintains the relative ordering and hence it is stable.
QUICK SORTMERGE SORT
Splitting of array depends on the value of pivot and other array elementsSplitting of array generally done on half
Worst-case time complexity is O(n2)Worst-case time complexity is O(nlogn)
It takes less n space than merge sortIt takes more n space than quick sort
It works faster than other sorting algorithms for small data set like Selection sort etcIt has a consistent speed on any size of data
It is in-placeIt is out-place
Not stableStable

Learn about Bubble sort

This brings us to the end of this article where we learned about Quik sort and its implementation in C, C++, Java and python. Improve your programming skills by taking up this free course by Great Learning academy. Click the banner below to know more.

quick sort
0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

twenty − twelve =