Home Arrays Quick Sort

Quick Sort

by nikoo28
2 comments

This algorithm is one of the specific ones people generally have a problem to understand. We will try out best to simplify it and understand it.
Basically quick sort comprises of these steps:-

  1. Choose a pivot element (it can be any random element in array)
  2. In one iteration keep all the numbers smaller to it on the left side and larger to it on the right side.
    (smaller numbers)_ _ _[PIVOT]_ _ _(larger numbers)
  3. Now we have the left sub-array of (small numbers) and the right sub-array (large numbers)
  4. Repeat steps 1 and 2 recursively on both the sub-arrays until we are left with just single elements.
  5. This should give you the final sorted array.

Illustration

Quick Sort works on the principle of Divide and Conquer algorithmic paradigm. The image below will illustrate the concept in a better way. In this example, we are choosing the first element of the array as the pivot element. The selected pivot element is represented in blue.

quick sort with first element as the pivot element.
Fig: Illustration of quick sort

Algorithm

Basically, we can choose any element as the pivot element. The algorithm for quick sort will be therefore:-

# choose pivot swap a[1, rand(1, n)] # 2-way partition k = 1 for i = 2:n, if a[i] < a[1], swap a[++k, i] swap a[1,k] → invariant: a[1..k-1] < a[k] <= a[k+1..n] # recursive sorts sort a[1..k-1] sort a[k+1, n]

Now let us take an example with array

arr[] = {2, 6, 4, 10, 8, 1, 9, 5, 11, 7};

And we will choose the last element as the pivot element.

  1. PIVOT = 7 or arr[10]
  2. Now we apply the iteration in the range 0-9 , leaving the pivot.
  3. We start from the left side, keeping “i” as a pointer
    • if(2 < pivot)  => move ahead (i = 0)
    • if(6 < pivot)  => move ahead (i = 1)
    • if(4 < pivot)  => move ahead (i = 2)
    • if(10 < pivot) => NO, STOP (i = 3 and points to 10)
  4. Now we start from the right side, keeping “j” as a pointer
    • if(11 > pivot)  => move towards left (j = 8)
    • if(3 > pivot) => NO, STOP. (j = 7 and points to 5)
  5. If (i < j) , we swap them
    thus array is now {2, 6, 4, 5, 8, 1, 9, 10, 11, 7}
  6. Increment i and decrease j. (i = 4, j = 6)
  7. Again we start; i = 4 and points to 8 and; j = 6 and points to 9.
  8. Eventually, we will get the array as:- {2, 6, 4, 5, 1, 8, 9, 10 ,11, 7}
  9. Swap the pivot element with arr[i].
  10. Thus we have {2, 6, 4, 5, 1, 7, 9, 10, 11, 8}

This way when PIVOT = 7, all small elements are on the left and greater elements on the right. Repeat this process with the left and right sub parts to sort the complete array.

Code

Here is an implementation of the above algorithm:-

#include<stdio.h> //a simple function to swap two numbers void swap(int *i, int *j) { int temp = *i; *i = *j; *j = temp; } // a function to partition the array arr // having starting index as - start // and ending index as - end int partition(int arr[], int start, int end) { // we take the pivot to be the last element // that means all elements smaller // to it will be on left and larger on right int pivot = arr[end]; // taking i and j to define the range, we leave the pivot int i = start; int j = end-1; // loop till in range while(i <= j) { // keep moving till the left element is smaller than pivot while(arr[i] < pivot) i++; // keep moving left till right element is larger while(arr[j] < pivot) j--; // we need to swap the left and right if(i <= j) { swap(&arr[i], &arr[j]); i++; j--; } } // once partitioned, we need to put the pivot at correct place swap(&arr[i], &arr[end]); // return the position of pivot return i; } void performQuickSort(int arr[], int start, int end) { //the terminating condition for recursion if(start < end) { // get the partition index int p = partition(arr, start, end); // perform quick sort on left sub part performQuickSort(arr, start, p-1); // perform quick sort on right sub part performQuickSort(arr, p+1, end); } } //defining a function to perform merge sort on array arr[] of given size void quickSort(int arr[], int size) { performQuickSort(arr, 0, size-1); } // driver program to test the above function int main(void) { int i; int arr[10] = {2, 6, 4, 10, 8, 1, 9, 5, 3, 7}; quickSort(arr,10); printf("SORTED array:- "); for(i = 0; i < 10; i++) printf("%d ",arr[i]); return 0; }

Time Complexity: O(n * \log n)
Space Complexity: O(\log n)

You can also find the code and test cases on Github.

Video Explanation:

2 comments

You may also like

2 comments

Patrick June 26, 2015 - 02:36

In the #recursive sorts, at the last item, where it says “Thus we have {2,6,…,11,7}”, shouldn’t the “7” be an “8”? Great app, btw.

Reply
nikoo28 June 30, 2015 - 19:55

Thanks for pointing out the type Patrick.
I have corrected it. :)

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More