QuickSort — Coding Interview Preparation — Hackerrank In Top 30 MAANG question — SQL

1. A divide-and-conquer algorithm called Quicksort (also known as Partition Sort)
2. We write a method called partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number called pivot.
3. When partition is called on an array, two parts of the array get ‘sorted’ with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.

Explanation
This is a diagram of Quicksort operating on the sample array:

Code:

1. Non-inplace version

def quicksort(ar):
    if len(ar) <= 1:
        return ar
    lt, eq, rt = [], [], []
    # assuming there that ar[0] is the pivot
    for item in ar:
        if item < ar[0]:
            lt.append(item)
        elif item > ar[0]:
            rt.append(item)
        else:
            eq.append(item)
    sub = quicksort(lt) + eq + quicksort(rt)