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.
Advertisements
