So I understand how the partition works, however, I do not understand how the quicksort function works. This is code I found online however, most versions are pretty similar. How does the quicksort function piece together the entire sorted list? I don't understand how the return statement returns a whole sorted list when the partitions are making subsets of the list. So shouldn't the return value here be one or two numbers?
What I'm looking for is an explanation for how the_quicksort()function runs, step by step. Anyone's help is much appreciated!
def partition(xs, start, end):
follower = leader = start
while leader < end:
if xs[leader] <= xs[end]:
xs[follower], xs[leader] = xs[leader], xs[follower]
follower += 1
leader += 1
xs[follower], xs[end] = xs[end], xs[follower]
return follower
def _quicksort(xs, start, end):
if start >= end:
return
p = partition(xs, start, end)
_quicksort(xs, start, p-1)
_quicksort(xs, p+1, end)
def quicksort(xs):
_quicksort(xs, 0, len(xs)-1)
This is an example of Lomuto partition scheme were partition() separates the input into values <= pivot, pivot, values > pivot. The result of this is that the values <= pivot will be swapped so they are less than (follower-start) away from their final sorted position, values > pivot will be swapped so they are less than (end-follower) away from their final sorted position, and pivot (xs[end]) will be placed in it's sorted position. Then it recursively calls itself for the left and right groups. Each level of recursion for a group puts the elements in that group closer to their final sorted position, and once a base case is reached (0 or 1 elements), that element is in its final sorted position.
You can think of this as the data becomes closer to being sorted with each level of recursion, and once the entire recursion stack tree has been traversed, the array ends up sorted.
Although quick sort is often called a divide and conquer method, the work done by swapping elements closer to their final sorted position is done before division, and once division reaches a base case of 1 element, that element is now in it's final sorted position, and nothing is done during the returns back up the call chain.
Take a look at
https://en.wikipedia.org/wiki/Quicksort#Algorithm
https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme