Quick Sort

Quick Sort is a very popular sorting algorithm. It is based on the "Divide on Conquer" paradigm which in simple words means to divide the array into smaller parts and then sort the smaller parts to get the larger sorted output.

Algorithm:

The algorithm uses recursion to divide the problem into smaller parts.
It mainly has 2 functions:

1. partition(arr, low, high):-

It is the heart of the quick sort algorithm which sorts the array.
It selects the last element as a pivot.
At each call of partition, the correct place of pivot in the sorted array is returned. 
All the elements greater than the pivot are placed after the pivot and all the elements smaller than the pivot are placed before the pivot.

1. partition(arr, low, high):
2.      pivot = arr[high]
3.      i = low - 1
4.      for j = low to (high - 1)
5.          if(arr[j] <= pivot)
6.              i = i + 1
7.              swap arr[j] and arr[i]
8.      swap arr[i+1] and arr[high]
9.      return i+1

Example:- 

let arr = [2, 5, 4, 6, 1, 3]
low = 0, high = 5
initially i = low - 1 = -1
pivot = arr[high] = 3

1.  j = 0, arr[j] = 2
    arr[j] < pivot  -> i = i + 1 = 0
                    -> swap(i,j) -> arr = [2, 5, 4, 6, 1, 3]
                    
2.  j = 1, arr[j] = 5
    arr[j] > pivot  -> skip
    
3.  j = 2, arr[j] = 4
    arr[j] > pivot  -> skip
    
4.  j = 3, arr[j] = 6
    arr[j] > pivot  -> skip
    
5.  j = 4, arr[j] = 1
    arr[j] < pivot  -> i = i + 1 = 1
                    -> swap(i,j) -> arr = [2, 1, 4, 6, 5, 3]

6.  j = 5, j = high -> stop loop

7.  i = 1, high = 5
    swap(i+1, high) -> arr = [2, 1, 3, 6, 5, 4]

8.  return i+1 //that is 2

Notice that, if the array was sorted, that is arr = [1, 2, 3, 4, 5, 6], element 3 would have been at index 2, the value, which the partition function returned. Hence at each call, the partition function places the pivot element at its correct position.

Also, all the elements larger than 3 are now placed after index 2 and all the elements smaller than 3 are now placed before index 2.

2. quick_sort(arr, low, high):-

The quick_sort function calls the partition function on the array to get the pivot's correct location, and then recursively calls the quick_sort function on the elements to the left and right of the pivot to sort them recursively.

1. quick_sort(arr, low, high):
2.      if low < high:
3.            p = partition(arr, low, high)
4.            quick_sort(arr, low, p - 1)
5.            quick_sort(arr, p + 1, high)

Example:

let arr = [2, 5, 4, 6, 1, 3]

1.  quick_sort(arr, 0, 5) // arr = [2, 5, 4, 6, 1, 3]
    low = 0, high = 5 
    low < high:
        p = partition(arr, 0, 5) = 2    // updated arr = [2, 1, 3, 6, 5, 4]
        quick_sort(arr, 0, 1)   // arr = [2, 1]
        quick_sort(arr, 3, 5)   // arr = [6, 5, 4]

2.  quick_sort(arr, 0, 1) // arr = [2, 1]
    low = 0, high = 1 
    low < high:
        p = partition(arr, 0, 1) = 0    // updated arr = [1, 2, 3, 6, 5, 4]
        quick_sort(arr, 0, -1)  // low > high -> end
        quick_sort(arr, 1, 1)   // low = high -> end
    
3.  quick_sort(arr, 3, 5)   // arr = [6, 5, 4]
    low = 3, high = 5
    low < high:
        p = partition(arr, 3, 5) = 3    // updated arr = [1, 2, 3, 4, 5, 6]
        quick_sort(arr, 3, 2)   // low > high -> end
        quick_sort(arr, 4, 5)   // arr = [5, 6]
        
4.  quick_sort(arr, 4, 5)   // arr = [5, 6]
    low = 4, high = 5
    low < high:
        p = partition(arr, 4, 5) = 5    // updated arr = [1, 2, 3, 4, 5, 6]
        quick_sort(arr, 4, 4)   // low = high -> end
        quick_sort(arr, 5, 5)   // low = high -> end
        
Finally the sorted arr = [1, 2, 3, 4, 5, 6]

Google Search: QuickSort

Code in Python:

# Python program for implementation of Quicksort Sort by taking last element as pivot

def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]  # pivot

    for j in range(low, high):

        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


# Function to do Quick sort
def quickSort(arr, low, high):
    if low < high:
        # pivot is set to its right position after partition call
        pi = partition(arr, low, high)

        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)


# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
print("Before sorting array is:")
for i in range(n):
    print(arr[i], end=' -> ')
print('end')

quickSort(arr, 0, n - 1)

print("Sorted array is:")
for i in range(n):
    print(arr[i], end=' -> ')
print('end')

"""
Outputs:
Before sorting array is:
10 -> 7 -> 8 -> 9 -> 1 -> 5 -> end
Sorted array is:
1 -> 5 -> 7 -> 8 -> 9 -> 10 -> end
"""

Time Complexity:

1. Worst Case:

When the array is already sorted, sorted in reverse order or all the elements are equal, QuickSort runs in O(n²) time.

The reason is simple, quicksort makes uses of the divide and conquer approach to solve the problem of smaller sizes. In the case of a sorted array, each of the pivot chosen is already in its correct location, hence the recursive call divided the array of n elements into an array of only (n-1) elements.

Example: 

arr = [1, 2, 4, 7, 9]

quick_sort(arr, 0, 4)
    p = partition(arr, 0, 4) = 4
    quick_sort(arr, 0, 3)   // arr of n-1 elements
    quick_sort(arr, 5, 4)   // end

Each partition() function call does O(n) work.
If the problem gets reduced to only n-1 elements then quick_sort() will be called O(n) times which in turn will call partition() O(n) times.
Hence total time complexity = O(n*n) = O(n²)

2. Best or Average Case:

In the Best case, the array will be in such a form that the selected pivot always comes in the middle of the array.

In such a case the array will always be divided into two (n-1)/2 problems.
The total number of recursive calls of quick_sort() will not exceed O(log n).
Hence the total time complexity = O(n * log n) = O(n log n).

Even if the ratio in which the array gets divided is 1:9 or 1:999 the time complexity will still be O(n log n).
Hence quicksort performs fairly well in most of the cases except for the worst cases.

Here is the code in C language: QuickSort in C

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal