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.