Quick Sort—Python

Quick sort is a sorting algorithm that uses recursion and nested loops to sort items. Here is an implementation in Python

def split_list(unsorted, low, high):
    # Set our temp item at the low end
    item = unsorted[low]

    # Variables for tracking left and right
    # side of the list
    left = low
    right = high

    # loop until our left side is less than right side
    while left < right:

        # Move left to the right while it's less than item
        while unsorted[left] <= item and left  item:
            right -= 1

        # Check if we need to swap elements
        if left  low:
        # Split unsorted into two lists
        index = split_list(unsorted, low, high)

        # Sort the left hand of the list using recursion
        quick_sort(unsorted, low, index - 1)

        # Sort the right hand of the list using recursion
        quick_sort(unsorted, index + 1, high)


if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    quick_sort(items, 0, len(items) - 1)
    print(items)

When run, this code will produce the following output

['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Louise Belcher', 'Tina Belcher']

The key in this algorithm is that we split our list into two halfs and then use recursion to sort each half. The work of swapping elements takes place in the split_list function. However, the quick_sort function is responsible for calling split_list until all items are sorted.