Quicksort algorithm in C

Quicksort Algorithm

Quicksort is a sorting method which uses divide and conquer technique. Basic idea of algorithm is to divide the inputs around a pivot and then sort the two part one on the left side and other right.

In this article we will learn about the quicksort algorithm, code for it and then how we can apply modified quick sort on problems. Best part of quicksort algorithm is that it removes need of extra space required in merge sort. However, it also comes with a caveat that is input space may not be always divided into into two halves equally which can degrade the performance of algorithm considerably. We will see when this case arises.

Don’t want to read? Watch video here :

Quicksort algorithm

We will understand algorithm using an example. Let’s we have an array of integer A  = [3,4,10,5,6,7,9,10,19,2,1]. There are three parts of algorithm :

1. Select a pivot and then place it at it’s correct position.
2. Once pivot is on it’s place, sort left part of the array.
3. Then sort the right part.

Step 2 and 3 can be easily implemented in recursive function.

Step 1: Partition 
Select first element of input space i.e. A[0] as pivot pivot  = A[0].  Put this pivot into correct position such that all the elements on the left side of the pivot are smaller than pivot and on right side are greater than pivot. 
a. Start from the next element in input space and find the first element which is greater than pivot which was selected above. Let that be ith position.
b. Start from end of array and find first element from end which is smaller than pivot selected. Let it be jth position.
If i and j have not crossed each other i.e i<j then swap element at ith and jth positions, and repeat a dn b.
Once i and j cross each other, swap pivot with element at jth position.  After this step, pivot will be at its correct position and array will be divided into two parts, one on to the left side of pivot and other on to right side.

For input array A  = [3,2,19,10,6,7,10,1,4,5] below diagram shows the pivot and execution of function.

quicksort algorithm

We can see that all the elements on left side of pivot are less and right are greater than pivot. So our pivot is now at correct position.

Step 2 : Sort
Apply quick sort algorithm on the left part of array.Once can repeat the step one till we have a single or only two elements.

Step 3: Sort
This is same step as step two applied on right part of the array.

Complete code 

Quick sort example

Worst case behavior of quick sort is notoriously O(n2), when the input set is all sorted and pivot is either first or last element of array.
Worst case of quicksort happens when input array is already sorted in increasing or decreasing order. In this case, array is partitioned into two subarrays, size of one is 1 and the second is of size n-1. Similarly when we work on subarray with n-1 elements it is again divided into two subarrays of size 1 and n-2. In order to completely sort array it will split for n-1 times and each time it requires to traverse n element to find correct position of pivot. Hence the overall complexity of quicksort comes out as O(n2),In average case if pivot is picked wisely, quick sort can perform sorting in O(nlogn). 
Best part is there is no extra space involved in it.

Selection of Pivot 

If array is completely sorted, then worst case behavior of quicksort is O(n2), so there comes another problem. How can we select pivot so that we have two sub arrays are nearly halves of the input array. There are many solutions proposed.
1. Taking median of array as pivot. So how to select median of an unsorted array. We look into this problem separately, but yes it guarantees two halves of same size.
2. Selecting pivot randomly. This requires heuristics algorithms to select pivot. 

This is basic article explaining the concept of quicksort. In next post we would see how we can use this algorithm to find out Kth largest or smallest element in an array of integers.

Things to ponder on

  1. Is quick sort stable?
  2. No it is not.
  3. Is it suitable for parallel execution ?
  4. Can we use insert sort when we have small number of elements in a sub array? Left as an exercise.
Yes, we can run left and right sub arrays on parallel machines and then combine results to form the larger array.

Please leave your comment in case you find something wrong or you have some improved version.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s