Table of contents
- What is Quick Sort
- Quick Sort Pseudocode
- Quick Sort Algorithm
- Quick Sort Time Complexity
- Quick Sort Space Complexity
- Quick Sort in C
- Quick Sort in Java
- Quick Sort in C++
- Quick Sort in Python
- Quick Sort Example
- 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 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
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 111Quick 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
- Follow quicksort approach by taking 0 as Pivot
- Partition the array around a pivot
- Now we will be having negative elements on the left-hand side and positive elements on the right-hand side.
- Take 2 index variable, neg=0 and pos=partition index+1
- 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:
- Take a partitioned index p = -1 and traverse all the elements
- 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 SORT | MERGE SORT |
| Splitting of array depends on the value of pivot and other array elements | Splitting 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 sort | It takes more n space than quick sort |
| It works faster than other sorting algorithms for small data set like Selection sort etc | It has a consistent speed on any size of data |
| It is in-place | It is out-place |
| Not stable | Stable |
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.
