Fastest Sorting Algorithm

In this article, we will learn which is the fastest sorting algorithm, the fastest sorting algorithm with an example dry-run, what is the fastest sorting algorithm, and how to write the program for the fastest sorting algorithm.

Which is the Fastest Sorting Algorithm?

Quick sort is the fastest sorting algorithm. The quick sort algorithm works in O(n*logn) time for the best and average cases. Now, we will understand the quick sort(fastest sorting algorithm) in detail.

What is Selection Sort?

In the selection sort algorithm, first, a random element is picked up from an array which is called the pivot. The pivot divides the array into two parts and this process continues until the array becomes sorted.

There are various ways to select the pivot element from the array.

• Select the first element as the pivot element
• Select the last element as the pivot element
• Select the random element as the pivot element
• Select the median element as the pivot element

After selecting a pivot, we need to partition around that pivot. The partition() function is very important in quick sorting. If we selected pivot p after that, we need to put all the smaller elements than p to the left side of p and all the greater elements to the right side of the p. Let’s see how the partition() function works using an example.

In the above example, first, we have chosen the last element (5) as a pivot element and we can see that we have divided the array into two subarrays around 5. For the left subarray, we have again chosen the last element (4) as a pivot and we did partition around 4. For the right subarray, we have again chosen the last element (8) as a pivot and we did partition around 8. We will repeat this process until the partition size is less than or equal to 1.

Pseudo code for the Quick Sort (fastest sorting algorithm):

Pseudo code for the Quick Sort:

quick_sort(array[], low, high){
    if(low < high){
        // find the right position for the pivot element
    p=partition(array, low, high)

    // perform quick_sort on the left subarray
    quick_sort(array[], low, p-1)

        // perform quick_sort on the right subarray
    quick_sort(array[], p+1, high)
    }
}

Pseudo code for the partition():

partition(array[], low, high){
    // select the last element as a pivot
    pivot = array[high];  

    i = (low – 1)  // Index of the smaller element and indicates the 
    // right position of pivot found so far

    for (j = low; j <= high- 1; j++){

        // If the current element is smaller than the pivot
        if (array[j]  pivot (80 > 30) so we will not do anything and move ahead.

Quick Sort (Fastest Sorting Algorithm) with an Example Dry-Run:

Let’s take an example to understand how partition works in the quick sort algorithm.

First, we will choose the pivot element from the above array.
pivot = last element = 30

We will also initialize two variables,
i=0
j=0

Now, let’s see how the partition() function works.

Run a loop for j = low to j = high-1

First pass (i=0, j=0):
We will compare arr[j] with pivot, in this case, arr[0] > pivot (80 > 30) so we will not do anything and move ahead.

Second pass (i=0, j=1):
We will compare arr[j] with pivot, in this case, arr[1] > pivot (70 > 30) so we will not do anything and move ahead.

Third pass (i=0, j=2):
We will compare arr[j] with pivot, in this case, arr[2] > pivot (60 > 30) so we will not do anything and move ahead.

Fourth pass (i=0, j=3):
We will compare arr[j] with pivot, in this case, arr[3] 30) so we will swap arr[i] (80) and arr[j] (20) and increment the value of i.

After performing the swap, the array will look like the one below.

Fifth pass (i=0, j=4):
We will compare arr[j] with pivot, in this case, arr[4] 30) so we will swap arr[i] (70) and arr[j] (10) and increment the value of i.

After performing the swap, the array will look like the one below.

Sixth pass (i=0, j=5):
We will compare arr[j] with pivot, in this case, arr[5] > pivot (900 > 30) so we will not do anything and move ahead.

After completion of all the passes, in the end, we will swap arr[i] (60) and pivot (30).

After performing the swap, the array will look like the one below.

In the above image, we can see that the pivot element (30) is in its right position. All the elements left to the pivot are smaller than the pivot and all the elements right to the pivot are greater than the pivot.

Quick Sort Program:

We know how quick sort algorithm work. Now, let’s see how to write the program for quick sorting (the fastest sorting algorithm).

# Python3 implementation of QuickSort

def partition(array, low, high):
    pivot = array[high]

    i = low - 1
    for j in range(low, high):
        if array[j] <= pivot:
            i = i + 1
            # Swapping element at i with element at j
            array[i], array[j] = array[j], array[i]

    # Swap the pivot element with element at index i
    array[i + 1], array[high] = array[high], array[i + 1]

    # Return the position from where partition is done
    return i + 1


def quick_sort(array, low, high):
    if low < high:

        # Find position of pivot element
        p = partition(array, low, high)

        # perform quick sort on left part
        quick_sort(array, low, p - 1)

        # perfrom quick sort on right part
        quick_sort(array, p + 1, high)



array = [10, 7, 8, 9, 1, 5]

print(f'Array before performing quick sort: {array}')

quick_sort(array, 0, len(array) - 1)

print(f'Array after performing quick sort: {array}')

Array before performing quick sort: [10, 7, 8, 9, 1, 5]
Array after performing quick sort: [1, 5, 7, 8, 9, 10]

FAQs Related to Quick Sort Algorithm

1) The Quick Sort algorithm is in place?
Yes, the Quick Sort algorithm is in place. We are using extra space only to store recursive function calls.

2) The Quick Sort algorithm is stable?
This default Quick Sort algorithm is not stable. Though, we can make the Quick Sort algorithm stable by considering the index for comparisons.

3) Why Quick Sort is preferred over Merge Sort?
In the Quick Sort algorithm, we do not require any extra space. While, in Merge Sort, we require O(n) extra space where n is the size of the array. This extra space of Merge Sort used for allocation and de-allocating takes much time and that is why Quick Sort is preferred over Merge Sort.

4) What are other ways to implement the Quick Sort algorithm?
We can also implement quick sorting using the iterative method. The Quick Sort can also be implemented using a singly linked list and a doubly linked list.