The second sorting algorithm I decided to learn was the QuickSort. It’s a little more complicated than the StraightSort, but generally faster for larger numbers of integers.
The idea is to look at the first number of a list, call it the firstElement. You scan up the list looking for a number greater than the firstElement. Once you’ve found one, you scan down from the end of the list looking for a number less than the firstElement. When you’ve found both, swap them. Repeat this process till all the numbers greater than the firstElement are further down the list than all the numbers lower than the firstElement.
Congratulations, you’ve sorted the list with respect to the firstElement! Now, snip the firstElement off the front of the list, and slip it back into the list at the point where your probe scanning down the list first passed your probe scanning up the list. You’ve got the firstElement placed correctly in the list.
Now, break your list into two parts: one part extends from the beginning of the list up to the newly-placed firstElement, and the second part extends from just past the firstElement to the end of the list. Do the same “take the first Element and scan up from the list…” work you did before on the whole list, but this time do it to each part separately.
When the partial lists get down to around 7 elements or less, go ahead and do a StraightSort on them instead of the swap-and-scan sorting. When you’ve got the parts sorted, put them back together, and you’ve got a fully sorted list!
This one took me a while to wrap my head around, so don’t be intimidated if it doesn’t make sense at first. Have a look at the code below, and remember that you’re doing a sort on the whole list, then breaking it down and doing the same kind of sort on parts of the list, and so on down the line.
Here’s the code:
def quickSort(data):
“““Takes a list of integers and returns a sorted list.
Based on QuickSort method
Note: will not sort non-unique items!”””
insertedElement = data[0]
swappedData = swapSort(data)
insertedIndex = swappedData.index(insertedElement)
firstHalf = swappedData[:insertedIndex + 1]
if (insertedIndex != (len(swappedData) - 1)):
secondHalf = swappedData[insertedIndex + 1:]
else:
secondHalf = swappedData[insertedIndex:]
if len(firstHalf) > 7:
firstHalf = quickSort(firstHalf)
else:
firstHalf = straightSort(firstHalf)
if len(secondHalf) > 7:
secondHalf = quickSort(secondHalf)
else:
secondHalf = straightSort(secondHalf)
sortedData = firstHalf
sortedData.extend(secondHalf)
return sortedData
def swapSort(data): “““This is the first half of the QuickSort algorithm. Implemented here to prevent recursion errors””” firstElement = data[0] greaterIndex = 1 lesserIndex = len(data) - 1 while (lesserIndex >= greaterIndex): if (data[greaterIndex] > firstElement) & (data[lesserIndex] < firstElement): greater = data[greaterIndex] data[greaterIndex] = data[lesserIndex] data[lesserIndex] = greater greaterIndex += 1 lesserIndex -= 1 else: if data[greaterIndex] firstElement: lesserIndex -= 1 data.insert(greaterIndex, firstElement) data = data[1:] return data
Notice how I’ve broken up the algorithm into two functions: one that does the swap-and-scan, the other that breaks the list up and decides whether or not to run a StraightSort on the pieces. Again, I’m not sure I’ve fully Pythonized this code; any suggestions?
