Quick Sort

As Name Suggest, it shorts any list quickly. Quick sort is not a stable search, but it is very fast and requires very less additional space. It is based on the rule of Divide

and Conquer(also called partition-exchange sort).  In quick sort all the heavy lifting(major work) is done while dividing the array into subarrays, while in case of merge sort, all the real work happens during merging the subarrays. In case of quick sort, the combining step does absolutely nothing.

It is also called partition-exchange sort. This algorithm divides the list into three main parts :

1.    Elements less than the Pivot element.

2.    Pivot element(Central element)

3.    Elements greater than the pivot element

Pivot element can be any element from the array, it can be the first element, the last element or any random element. In this tutorial, we will take the rightmost element or the last element as pivot.

For example: In the array {68, 36, 63, 14, 17, 8, 6, 25}, we take 25 as pivot. So after the first pass, the list will be changed like this.

{6 8 17 14 25 63 36 68}

The algorithm starts by picking a single item which is called pivot and moving all smaller items prior to it, while all greater elements in the later portion of the list. This is the main quick sort operation named as partition, recursively repeated on lesser and greater sub lists until their size is one or zero - in which case the list is wholly sorted. Choosing an appropriate pivot, as an example the median element is the essential for avoiding the severely reduced performance of O(n^2).

Quick Sort Explanation:

The basic concept of quick sort process is pick one element from an array and rearranges the remaining elements around it. This element divides the main list into two sub lists. This chosen element is called pivot. Once pivot is chosen, then it shifts all the elements less than pivot to left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.

In the list of elements, mentioned in above  example, we have taken 25 as pivot. So after the first pass, the list will be changed like this.

6 8 17 14 25 63 36 68

Hence after the first pass, pivot will be set at its position, with all the elements smaller to it on its left and all the elements larger than to its right. Now 6 8 17 14 and 63 37 52 are considered as two separate lists, and same logic is applied on them, and we keep doing this until the complete list is sorted.

How Quick Sorting Works?

Following are the steps involved in quick sort algorithm:

1    After selecting an element as pivot, which is the last index of the array in our case, we divide the array for the first time.

2.    In quick sort, we call this partitioning. It is not simple breaking down of array into 2 subarrays, but in case of partitioning, the array elements are so positioned that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.

3.    And the pivot element will be at its final sorted position.

4.    The elements to the left and right, may not be sorted.

5.    Then we pick subarrays, elements on the left of pivot and elements on the right of pivot, and we perform partitioning on them by choosing a pivot in the subarrays.

Let's consider an array with values {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}

Below, we have a pictorial representation of how quick sort will sort the given array.

 

In step 1, we select the last element as the pivot, which is 6 in this case, and call for partitioning, hence re-arranging the array in such a way that 6 will be placed in its final position and to its left will be all the elements less than it and to its right, we will have all the elements greater than it.

Then we pick the subarray on the left and the subarray on the right and select a pivot for them, in the above diagram, we chose 3 as pivot for the left subarray and 11 as pivot for the right subarray.

And we again call for partitioning


Quick Sort Pseudocode:

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Quick Sort in C Algorithm:

/*  a[] is the array, p is starting index, that is 0, 

and r is the last index of array.  */

void quicksort(int a[], int p, int r)    

{

  if(p < r)

  {

    int q;

    q = partition(a, p, r);

    quicksort(a, p, q);

    quicksort(a, q+1, r);

  }

}

int partition(int a[], int p, int r)

{

  int i, j, pivot, temp;

  pivot = a[p];

  i = p;

  j = r;

  while(1)

  {

   while(a[i] < pivot && a[i] != pivot)

   i++;

   while(a[j] > pivot && a[j] != pivot)

   j--;

   if(i < j)

   {

    temp = a[i];

    a[i] = a[j];

    a[j] = temp;

   }

   else

   {

    return j;

   }

  }

}

⇒Quick Sort in C Code: http://bit.ly/2VdPRkM
⇒Quick Sort in Python Code: http://bit.ly/2U1BChA

Complexity:

• Worst Case Time Complexity : O(n2)
• Best Case Time Complexity : O(n log n)
• Average Time Complexity : O(n log n)
• Space Complexity : O(n log n)

Notes:

• Space required by quick sort is very less, only O(n log n) additional space is required.
• Quick sort is not a stable sorting technique, so it might change the occurence of two similar elements in the list while sorting.