Quick Sort

What is quick sort?

Quick sort uses the divide-and-conquer approach based on the idea of choosing a pivot element from the array and partitioning the array around it where the Left side of pivot contains elements that are smaller than the pivot and Right side contains elements greater than the pivot.

The different ways to perform quick sort are:

• The last element is selected as the pivot (implemented below).
• The first element is selected as the pivot.
• The middle element is selected as the pivot.
• A random element is selected as the pivot.

Time and Space Complexity:

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

Prerequisites:

• Recursion

Steps:

1. In an array A of length ‘N’, take the last element as pivot.
2. Now let i be (A[0] – 1) and j be the A[N-1].
3. To find the sorted position of the pivot, start incrementing i till you find an element greater than the pivot. 
4. At the same time start decrementing j till you find an element lesser than or equal to the pivot.
5. Swap the elements present at i and j.
6. Repeat steps 3 and 4 until i has an element greater than j.
7. Swap the pivot with the element present at j.
8. Repeat the above steps for the left and right side of the pivot and you will have a sorted array at the end.

Pseudo code for quick sort:

low  --> Starting index,  high  --> Ending index
sortPivotPosition (A[], low, high)
{
    pivot = A[high];  
 
    i = (low - 1);

    for (j = low; j <= high- 1; j++)
    {
        if (A[j] < pivot)
        {
            i++;
            swap A[i] and A[j]
        }
    }
    swap A[i + 1] and A[high])
    return (i + 1)
}

quickSort(A[], low, high)
{
    if (low < high)
    {
        pivot = SortPivotPosition(A, low, high);

        quickSort(A, low, pivot - 1);  
        quickSort(A, pivot + 1, high);
    }
}

How can we visualize quick sort?

Let’s Code

To code in any language other than Python, 👉 Click here 👈