Quick Sort Recursive Python Program

Quick Sort is an effective sorting algorithm that makes the use of pivots. It is known as a divide-and-conquer algorithm which is a paradigm that recursively breaks down a problem into multiple sub-problems of the same type, until these individually are easy enough to be solved directly.

STEP 1: Select a pivot (e.g. first item, last item, median…)
STEP 2: Work your way through the unsorted list comparing each item you encounter against the pivot number. If it is greater than the pivot number, place it to the right of the pivot, and if it is less than the pivot number, place it to the left of the pivot. (REMEMBER to keep the order of the numbers the same)
STEP 3: Circle the pivot number used as this is now been used once.
STEP 4: Apply the same method again to the two sub-lists now created. This process is repeated until there are no more comparisons to make.

The worst case scenario has a complexity of:

Yet an average case takes:

The Code

Create a function called quick_sort that takes in an unsorted list as a parameter. Firstly, it checks whether the length of the sequence is just 1, in which case the sequence is sorted. If the length > 1, then the last element is returned and removed using the .pop() function. (This is our pivot)

By iterating through each item in the list, we check if the item is greater than or less than the pivot value. If greater than, it is appended to another list called greater_items, and if less than it is appended to a list called lesser_items.

The return statement of this function recursively calls upon itself to quick_sort the lesser_items and greater_items list as well, until all of the lists each have length of 1. This is how we know the quick_sort is completed.

def quick_sort(sequence):
    length = len(sequence)
    if length <= 1:
        return sequence
    else:
        pivot = sequence.pop() #remove and return last element 
    
    greater_items = []
    lesser_items = []

    for item in sequence:
        if item > pivot:
            greater_items.append(item)
        else:
            lesser_items.append(item)
    
    return quick_sort(lesser_items) + [pivot] + quick_sort(greater_items)

print(quick_sort([0,9,3,8,2,7,5]))

Output:

[0, 2, 3, 5, 7, 8, 9]