Quick Sort

2.1K

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.

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]Code language: PHP (php)

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;
}
Code language: C++ (cpp)

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

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

Video Explanation: