AI Features
Home
Courses
An Intro to Python 3

Puzzles 42 to 44

Understand quicksort algorithm, unpacking keyword arguments with dictionaries and infinite code.

We'll cover the following...

Puzzle 42

Which of the following functions correctly sorts the list?

Note: Enter the output you guessed. Then, press the Run button, and your new Elo will be calculated. Don’t forget to save your Elo rating.

Python 3.5
#############################
## id 195
## Puzzle Elo 1672
## Correctly solved 67 %
#############################
def qsort1(L):
  if L:
    return qsort1([x for x in L[1:] 
                  if x < L[0]]) + L[:1] \
                     + qsort1([x for x in L[1:] if x  >= L[0]])
  return []
def qsort2(L):
  if L:
    return L[:1] + qsort2([x for x in L[1:] 
      if x < L[0]]) \
         + qsort2([x for x in L[1:] if x  >= L[0]])
         
  return []
print(qsort1([0, 33, 22]))
print(qsort2([0, 33, 22]))

Quicksort

This puzzle introduces a recursive algorithm to sort lists. When executing the 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. Quicksort 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 ...

Ask