syntax.us Let the syntax do the talking
Blog Contact Posts Questions Tags Hire Me

Question:
In Python how to Quicksort?

I bumped into a Python quicksort example at this URL:

http://cs231n.github.io/python-numpy-tutorial/

How does Quicksort work?

I enhanced the above example so it will run on my laptop:

# myquicksort.py

# ref: 
# http://cs231n.github.io/python-numpy-tutorial/
import pdb

def quicksort(mylst):
    pdb.set_trace() # breakpoint
    if len(mylst) <= 1:
        return mylst
    pdb.set_trace() # breakpoint
    pivot_n = len(mylst) / 2
    # In Python how to round off decimal to integer?
    pivot_i = int(pivot_n)
    pivot   = mylst[pivot_i]
    # Use 'comprehension' to get members left of middle.
    left    = [x for x in mylst if x < pivot ]
    middle  = [x for x in mylst if x == pivot]
    # Use 'comprehension' to get members right of middle.
    right   = [x for x in mylst if x > pivot ]
    nxtlst  = quicksort(left) + middle + quicksort(right)
    pdb.set_trace() # breakpoint
    return nxtlst

pdb.set_trace()
quicksort([1,2,3])
Notice that I wrote in lines of debugging syntax.

This allows me to connect my mind to each line and each variable as the syntax walks forward.

Also I see quicksort() calling itself near the last line of the method.

So this implementation of quicksort() is recursive.

It is easy to explain a general behavior of the method by looking at that last line:
  • I divide the input-list into three pieces.
  • I sort the left piece.
  • I no-op the middle piece
  • I sort the right piece.
  • I concatenate the 3 pieces
That behavior is easy to understand.

It is more difficult to understand how the recursion stops once the list is sorted.

I stepped through the method with the debugger and captured a screen dump.

The debugger has simple behavior.

It runs the script until the debugger encounters a breakpoint.

Then it lists the line about to run.

When the debugger is stopped I can look at variable-values.

When I want to see a variable-value in the line:
  • I type in the name of the variable before the line runs.
  • I type in the name of the variable after the line runs.
  • Then I can see how the line changed the variable-value.
In the example below I use only two commands: c and n

The c command asks the debugger to run until it encounters a breakpoint I place in the code. After the debugger encounters the breakpoint it stops and displays the line of syntax about to be run.

The n command asks the debugger to run only 1 line and then stop and then show the next line about to run.

The debugger works well unless my code has a variable with the same name as a debugger command.

So, in my code, I avoid using variables named c or n:

dan@nia111:~/ks/b/cs231/lec01 $ 
dan@nia111:~/ks/b/cs231/lec01 $ 
dan@nia111:~/ks/b/cs231/lec01 $ python myquicksort.py 
-> quicksort([1,2,3])
(Pdb) c
-> if len(mylst) <= 1:
(Pdb) mylst
[1, 2, 3]
(Pdb) c
-> pivot_n = len(mylst) / 2
(Pdb) n
-> pivot_i = int(pivot_n)
(Pdb) n
-> pivot   = mylst[pivot_i]
(Pdb) n
-> left    = [x for x in mylst if x < pivot ]
(Pdb) n
-> middle  = [x for x in mylst if x == pivot]
(Pdb) n
-> right   = [x for x in mylst if x > pivot ]
(Pdb) n
-> nxtlst  = quicksort(left) + middle + quicksort(right)
(Pdb) left
[1]
(Pdb) middle
[2]
(Pdb) right
[3]
(Pdb) c
-> if len(mylst) <= 1:
(Pdb) mylst
[1]
(Pdb) c
-> if len(mylst) <= 1:
(Pdb) mylst
[3]
(Pdb) c
-> return nxtlst
(Pdb) nxtlst
[1, 2, 3]
(Pdb) c
dan@nia111:~/ks/b/cs231/lec01 $ 
dan@nia111:~/ks/b/cs231/lec01 $ 
dan@nia111:~/ks/b/cs231/lec01 $ 
When I watched the above debugger in action, my mind grasped the idea that recursion stops when quicksort() encounters a list with only one member.

Perhaps a more important observation is that I saw recursion stop when quicksort() encountered a sorted list of three members.

Then the next level of understanding came when saw that this expression:
nxtlst  = quicksort(leftlst) + middle + quicksort(right)
quickly becomes this expression:
nxtlst  = leftlst + middle + quicksort(right)
after leftlst is a sorted list of three members.

So, this quicksort() example is a good way to learn about:
  • Quicksort
  • Pdb-debugger
  • Python-comprehensions
  • len()
  • int()
  • Python-method-syntax
  • Python-if-then-syntax
  • Python-List-Concatenation
  • Recursion



syntax.us Let the syntax do the talking
Blog Contact Posts Questions Tags Hire Me