Quick Sort Python Recursion - how does the recursive function work

Question

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)

rcgldr · Accepted Answer · 2020-04-05 00:12:26Z

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

edited Apr 5, 2020 at 0:12

answered Apr 4, 2020 at 21:13

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

novice_programmer9623 Over a year ago

How does the program know to piece together all of the partitions into one sorted list?

rcgldr Over a year ago

@novice_programmer9623 - I updated my answer to explain this better. The partitions are not "pieced together". Instead each partition step in general swaps elements closer to their final sorted position, and once a base case is reached, at least one element is now in it's final sorted position.

Collectives™ on Stack Overflow

Quick Sort Python Recursion - how does the recursive function work

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related