Quicksort and its Implementation in ‘C’

Like Merge Sort, Quicksort is a divide and conquer algorithm. Quicksort first divides the array into two smaller sub-arrays around a picked element called Pivot. Then recursively sort the sub-arrays. It works as follows:

  1. Pick an element, called a pivot, from the array.
  2. Reorder the array such that all the elements before pivot are less than pivot value, while all elements after pivot are grater than or equal to pivot. After this operation, the pivot is in its final position. This is the key process in quicksort, called the partition().
  3. Recursively apply this to the sub-arrays before and after the pivot. Look at this example.

There are different variants of Quicksort that pick pivots in different ways:

  1. First element of array.
  2. Last element of array.(used in the following implementation)
  3. Random element of array.
  4. Middle index element of array.

Complexities

Time complexity : O( N log N --  N log N -- N² ) [Best -- Average -- Worst] 
Memory          :  O(N or log N) # auxiliary i.e. apart from storing input array 
Stable          :  No i.e. can change relative order of elements with same key
# N being the number of elements in the array

Other popular sorting algorithms’ complexities are given here.

Usage and advantages

Although the worst case time complexity of QuickSort is O(n2) which is more than many other sorting algorithms like Merge Sort and Heap Sort, QuickSort is faster in practice, because its inner loop can be efficiently implemented on most architectures, and in most real-world data. Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort function, hence it lent its name to the C standard library function qsort and in the reference implementation of Java.

Bottom Line: Quicksort is often faster in practice than other O(n log n) algorithms.

Implementation in C:

Question: Sort an array of integers in increasing order using quicksort algorithm (format similar to most of the online programming contests )

Input:

First line of the input contains T, number of test cases

Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.

Output: Sorted array

Sample Input

3
5 4 7 9 3 1
3 4 5 5
4 6 10 6 7

Sample Output

1 3 4 7 9
4 5 5 
6 6 7 10

Code

Brief explanation is given in the gist.

Advertisements

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