Quick Sort Algorithm with explanation

Data Structure

Quick Sort is also known as partition exchange sort which sorts elements using works a divide-and-conquer strategy to sort an array. In divide and conquer first divide an unsorted array into two smaller sub-arrays on the basic of pivot element and then further sub-array if possible. These sub-arrays are recursively called to sort the elements.

Quick Sort algorithm developed by C. A. R. Hoare which is a widely used sorting the elements of a list. In the average case, Quick Sort makes O(n log n) comparisons to sort an array of n elements. And in the worst case, it has a quadratic running time O(n2).

  • Quick sort is a recursive algorithm that follows a divide-and-conquer strategy.
  • The time complexity of the Quick Sort algorithm is O(nlogn) in the average case.
  • The time complexity of the Quick Sort algorithm is O(n2) in the worst case.
  • Quick Sort is an in-place sorting algorithm it means it takes an only a constant amount of memory to perform the sorting algorithm.
  • Quick Sort is often the efficient sorting algorithm that is used by most of the language libraries to perform sorting.

So in this lesson we will see working of Quick Sort algorithm with an example.

How does quick sort algorithm works?

Suppose we have an array arr which contains list of integers and we want to re-arrange this list in increasing order. So in Quick Sort first we select one of the elements from the array as pivot and then we re-arrange the array in such a way all the elements lesser than the pivot element are at the left of it and all the
greater elements than the pivot elements are towards the right.

Lets consider we have an array

arr = {14,5,12,8,2,11,7}

Quick Sort Algorithm

So here first we will select right most element as pivot means in this example 7 is choosen as pivot.

Now after rearranging the array, array arr will look likes

{5,2,7,8,14,11,12}

  • First pivot element is chosen from the array, 7 is chosen here as a pivot.
  • Also we have two variable pindex and i.
  • arr[i] is compared to pivot element, if arr[i] is smaller than the pivot and also greater than pindex then swap a[i] with pindex and increment pindex by 1.
  • Else if arr[i] is greater than pivot then just move forward by an increment of i. This process will run till i < n.
  • Now Pivot 7 is sorted so our array arr will be partitioned into sub array like

In this case now we have two pivot elements, one in each sub arrays.

Algorithm of quick sort

Quick Sort Pivot Algorithm


Step 1– Initialize an array arr
Step 2 − Choose the rightmost element as a pivot
Step 3 − Take two variables pIndex and i which is pointing to left most element excluding pivot
Step 4 − While value at arr[i] is less than pivot then swap arr[i] with pIndex, increase pIndex by 1
Step 5 − While value at arr[i] is greater than pivot increment i by 1
Step 6 − if both step 3 and step 4 does not match then swap pivot to pIndex
Step 7 − pIndex is now pivot
Step 8 – Follow step 2 to 6 to find a pivot for each sub array

Quick Sort Algorithm

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Time complexity of Quick Sort

Best-case performance: O(nlogn)
Average performance: О(nlogn)
Worst-case performance: О(n2)

Space Complexity: O(1)

Pseudo Code of Quick Sort

function swap(int a, int b)
	temp = a
	a = b
	b = temp
end of function 

function partitionFunc(arr, start, end)
   pivot=arr[end]
   pindex=start
   for i = start to end - 1
	if(arr[i] <= pivot)
		swap(arr[i], arr[pindex])
		pindex + 1
	end of if
   end of for
   swap(arr[pindex], arr[end])	
end function


procedure quickSort(arr, start, end)
   if(start<end) 
      pindex = partitionFunc(arr, start, end)
      quickSort(arr,start,pindex-1)
      quickSort(arr,pindex+1,end)    
   end if
end procedure

Quick Sort Program in C

#include<stdio.h>

void swap(int *a, int *b );
void quickSort(int *arr, int start, int end);

int partition(int *arr, int start, int end){
	int pivot = arr[end];
	int pIndex=start;
	for(int i=start; i<end; i++){
		if(arr[i]<=pivot){
			swap(&arr[i],&arr[pIndex]);
			pIndex++;
		}
	}
	swap(&arr[pIndex], &arr[end]);
	return pIndex;
}

void swap(int *a, int *b ){
    int temp = *a;
    *a=*b;
    *b=temp;
}
void quickSort(int *arr, int start, int end){
	if(start<end){
		int pIndex = partition(arr, start, end);
		quickSort(arr, start, pIndex-1);
		quickSort(arr,pIndex+1,end);
	}
}

int main(){
	 int arr[100],i,j,n,key;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
	quickSort(arr,0,n);
	printf("\n");
    printf("after sorting:\n");
	for(int i=0; i<n; i++)
		printf("%d \t",arr[i]);
    return 0;
}

Output:

Share on