Quick Sort Recursion

Question

I'm trying to trace this quick sort algorithm:

https://pythonschool.net/data-structures-algorithms/quicksort/

But with a different set of numbers - [6,2,8,4,3,7,10]

I'm fine once the left side of the algorithm is sorted, but I don't understand the recursion class after that.

Once the left side is completed and start = 0 and end = 0, the following line runs:

 quicksort(myList, pivot+1, end)

When I print out the start and end values from the quick sort function:

Start = 2 and End = 1
Start = 3 and End = 2
Start = 4 and End = 6

I don't understand how the start and end change to these values.

Can anyone explain how and why?

Некто Некто · Accepted Answer · 2017-02-23T15:12:14

You might consider a easier implementation of quicksort. For example,

my_list = [52,8,45,43,6,56,76,36,54,12,34,98,41,30]

def quicksort(arr):
    high = []
    low = []
    pivot_list = []

    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                low.append(i)
            elif i > pivot:
                high.append(i)
            else:
                pivot_list.append(i)
        high = quicksort(high)
        low = quicksort(low)

    return low + pivot_list + high

print quicksort(my_list)

[6, 8, 12, 30, 34, 36, 41, 43, 45, 52, 54, 56, 76, 98]

This rather simple implementation is easy to explain. You are partitioning a list based on an arbitrary choice of the pivot. In this case arr[0] = 52. You then are iterating through the list and if the element is greater than the pivot (52), you put it into the 'high' partition and if it's less than 52, you're putting it into the 'low' partition. At this point after one run through (before we run high = quicksort(high)), we have

low = [8, 45, 43, 6, 36, 12, 34, 41, 30]
high = [56, 76, 54, 98]
pivot_list = [52]

We then run this quicksort function on the 'low' and 'high' partitions. For example, for the high partition, pivot = arr[0] = 56. We iterate through the high partition, and if the element is less than the pivot(56), we put it in a new low partition group that is a subgroup of the high partition. If the element is greater than 56, then we put it in a new high partition that is a subgroup of the high partition. You can think of it as starting with one list that we want to sort and branching off into a high partition and a low partition which then each branch into their own high and low partitions. That's where the recursion comes in

Quick Sort Recursion

1 Answers