Let me start with a question. Have you ever been to a school prayer or assembly? How do you stand there? Based on height. When you are asked to arrange among yourselves, students know that one is the tallest and the other is the smallest of all. They stand at both ends. The remaining would arrange accordingly by comparing heights. So, how it can be relatable to our Quick sort? What we do here is we will choose an element in the list of elements, called the pivot, and arrange the other elements by comparing them with the pivot. Let’s see how!!
We are free to choose any random element from the list as the pivot. Here we consider the middle element as the pivot. We shall also discuss the consequences of choosing different pivots.
Algorithm:
- From the list of elements choose any element as the pivot (here the middle element).
- After selecting the pivot, divide the array into two parts. Here the division is known as partitioning.
- Partitioning doesn’t mean that dividing the array or the list of elements into two halves. The array is divided in such a way that the elements greater than the pivot will be to the right of the pivot and the elements lesser than the pivot will be to the left of it.
- The pivot element is in its sorted position whereas the elements to the right and left to it are unsorted.
- Again, we implement the partition on the left and right sub-arrays of the pivot recursively.
Pseudocode:
start procedure
partition(arr,l,h)
pivot ← arr[(l+h)/2]
i←l
j←h
while i<j do
if arr[i]<=pivot then
i←i+1
end if
if arr[j]>pivot then
j←j-1
end if
if i<j then
temp←arr[l]
arr[i]←arr[j]
arr[j]←temp
end if
end while
temp←arr[l]
arr[l]←arr[j]
arr[j]←temp
end procedure
start procedure
quicksort(arr,l,h)
if l<h then
r←partition(arr,l,h)
quicksort(arr,l,r)
quicksort(arr,r+1,h)
end if
end procedure
Implementation of Quick sort in Java:
import java.util.*;
class QuickSort {
static int n,i,j,temp,step=0;
static Scanner sc =new Scanner(System.in);
static int partition(int [] arr,int l,int h){
step++;
int pivot=arr[(l+h)/2];
i=l;j=h;
while(i<j){
if(arr[i]<=pivot)
i++;
if(arr[j]>pivot)
j--;
if(i<j){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
temp=arr[l];
arr[l]=arr[j];
arr[j]=temp;
System.out.print("\n At " + step + " the arrangement is: ");
for(i=0;i<n;i++)
System.out.print(arr[i]);
return j;
}
static void quicksort(int [] arr,int l,int h){
if(l<h){
int r=partition(arr,l,h);
quicksort(arr,l,r);
quicksort(arr,r+1,h);
}
}
public static void main(String [] args){
System.out.println("Enter the size of the array: ");
n=sc.nextInt();
int[] arr=new int[n];
System.out.println("Enter the elements of the array: ");
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
quicksort(arr, 0, n-1);
System.out.println("\n The ordered array of elements is: ");
for(i=0;i<n;i++)
System.out.print(" " +arr[i]);
}
}
Notations:
arr → Array of elements to be sorted
i,j → Variables used in loops
l → least index of array
h → highest index of array
pivot → element selected to sort
r → the index at which the pivot is placed or
the sorted index of pivot
temp → temporary variable to swap elements
partition function → function used to section the elements
quicksort function → function used to sort the elements;
recursive use.
Time Complexity Analysis:
Time complexity worst case:
It is recommended to take the middle element as the pivot to decrease time complexity. Any random element can also be taken as pivot. But this gives sometimes the best and sometimes the worst case.
Space complexity is from log n (best case) to n (maximum)
Techprodezza 
2 thoughts on “Quick Sort”