QuickSort

Quicksort uses a divide and conquer approach to sorting an array, and leverages recursion.

Essentially, you pick a pivot number from the array to be sorted, it can be any number:

[4, 6, 2, 1, 5]

Let’s pick 2.

Now partition the array into two sub-arrays, the numbers less than or equal to the pivot are added to the first sub-array (less), those greater are added to the second sub-array (greater):

pivot   = 2
less    = [1]
greater = [4, 6, 5]

Note: Remember to skip the number you chose as a pivot when building your sub-arrays.

The last step is to recursively call quicksort on the two sub-arrays, joining the results to the pivot:

quicksort(less) + [2] + quicksort(greater)

Here’s the implementation, notice how we picked the first number in the array as our pivot, this makes it easy to skip.

def quicksort(array):
    if len(array) < 2:
        return array

    # pick the first number in the array
    pivot = array[0]

    less = []
    greater = []

    # skip our pivot number, start from the second
    for i in array[1:]:
        if i <= pivot:
            less.append(i)
        else:
            greater.append(i)

    return quicksort(less) + [pivot] + quicksort(greater)


print(quicksort([7, 11, 5, 2, 44, 21, 3, 18, 1]))

# outputs:

[1, 2, 3, 5, 7, 11, 18, 21, 44]

The same, more concisely:

def quicksort(array):
    if len(array) < 2:
        return array

    pivot = array[0]

    less = [x for x in array[1:] if x <= pivot]
    greater = [x for x in array[1:] if x > pivot]

    return quicksort(less) + [pivot] + quicksort(greater)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s