The Quicksort Algorithm in Python

Which function correctly sorts the list?

 

def qsort1(L):
    if L == []: return []
    return qsort1([x for x in L[1:] if x< L[0]]) + L[0:1] \ + qsort1([x for x in L[1:] if x>=L[0]])

def qsort2(L):
    if L == []: return []
    return L[0:1] + qsort2([x for x in L[1:] if x< L[0]]) \ + qsort2([x for x in L[1:] if x>=L[0]])

print(qsort1([0,33,22]))
print(qsort2([0,33,22]))

 

When executing both functions, you get the following results.

print(qsort1([0,33,22])) --> output: [0, 22, 33]
print(qsort2([0,33,22])) --> output: [0, 33, 22]

So, based on this output, the function qsort1 correctly sorts the list. But why? The algorithm is a variant of the popular quicksort algorithm. Quicksorts selects a pivot element from the list. In the puzzle, it selects the first element of the list, i.e., L[0]. Then, the algorithm moves all elements that are smaller than the pivot to the left side. Similarly, it moves elements that are larger or equal than the pivot to the right side.

This is repeated in a recursive manner for the left and the right lists. Suppose, you create a new list as follows. You put all elements that are smaller than the pivot on the left, then the pivot, then all elements that are larger or equal the pivot on the right. The resulting list feels a bit more sorted, right? If the two sublists were already sorted, the list would be perfectly sorted. This is where the recursive call of qsort1 comes into play. It takes over the problem of sorting each sublist by applying the same scheme of pivoting and recursion to the sublist.

In contrast, the qsort2 function appends both sublists to the right of the pivot element. Hence the list is already unsorted after the first recursion level.

Solving these kinds of puzzles regularly will boost your code understanding skills. They do not only train your language understanding but also your conceptual thinking which is even more important for coders at any level.


Are you a master coder?
Test your skills now!

Related Video

Solution

qsort1

 

Leave a Comment

Your email address will not be published. Required fields are marked *