# Quicksort best practices

aka

## Lambdaizing Python Code - a really usefull study ... NOT

This document describes how to convert a perfectly legal, typical python source into a lambda-only source. Along the way I hope to pass some tricks on how to use - or, rather, misuse - lambda.

## Getting started

Googeling for a python quicksort algorithm will give you the nicely commented one at http://www.hetland.org/python/quicksort.html. So, lets use that one, and start with the main quicksort function. Here it is in all detail:

def quicksort(list, start, end):
if start < end:
split = partition(list, start, end)
quicksort(list, start, split-1)
quicksort(list, split+1, end)
else:
return


The first rewrite reads like this:

def quicksort(list, start, end):
if start < end:
split = partition(list, start, end)
(quicksort(list, start, split-1),quicksort(list, split+1, end))
else:
return


Here, the two quicksort statements are placed inside a tuple to make them look like one expression. Why can't the first statement (the "split = ..." bit) be put into the tuple, also? Because it is a statement rather than an expression.

## Statements vs. Expressions

OK, back on track. We need to find a way to convert the assignment statement to an expression. In this specific case, the assignment actually is used to create a local variable partition. Local variables are best created by adding additional lambda calls, as you can see here:

def quicksort(list, start, end):
if start < end:
do_something = lambda split: (quicksort(list, start, split-1),
quicksort(list, split+1, end))
do_something(partition(list, start, end))
else:
return


So, you declare a lambda function for the code that uses the local variable, and then call the lambda function to actually create the local variable. To make this more compact, lambda style, we now can write:

def quicksort(list, start, end):
if start < end:
(lambda split: (quicksort(list, start, split-1),
quicksort(list, split+1, end)))(partition(list, start, end))
else:
return


The else: return bit is redundand, so it can be simply omited. For if-a-then-b we can use the logical conjunction a-and-b, so that gives us

def quicksort(list, start, end):
start < end and (lambda split: (quicksort(list, start, split-1),
quicksort(list, split+1, end)))(partition(list, start, end))


Final touches are renaming the arguments so they look more lambdaesque (list=l, start=s, end=e, split=p), and putting the thing inside lambda:

q = lambda l,s,e:s<e and (lambda p:(q(l,s,p-1),q(l,p+1,e)))
(partition(l,s,e))
quicksort = q


Now that was easy, wasn't it? But wait, there is still the partition function, and that one is a bit larger and more complex. Lets take a look at its original form:

def partition(list, start, end):
pivot = list[end]
bottom = start-1
top = end

done = 0
while not done:

while not done:
bottom = bottom+1

if bottom == top:
done = 1
break

if list[bottom] > pivot:
list[top] = list[bottom]
break

while not done:
top = top-1

if top == bottom:
done = 1
break

if list[top] < pivot:
list[bottom] = list[top]
break

list[top] = pivot



So where to start? Actually, there could be several starts, but lets focus on the big structure of the code first. The code has two inner while loops which can be expressed as functions:

def partition(list, start, end):
pivot = list[end]
bottom = start-1
top = end

def pf1():
while not done:
top = top-1
if top == bottom:
done = 1
break
if list[top] < pivot:
list[bottom] = list[top]
break

def pf2():
while not done:
bottom = bottom+1
if bottom == top:
done = 1
break
if list[bottom] > pivot:
list[top] = list[bottom]
break

done = 0
while not done:
pf1()
pf2()

list[top] = pivot


So, I just moved the inner while loops to separate functions, so that I can more easily focus on them in the next code bits. But wait, this code won't work. If you try to run it, you get the exception

Traceback (most recent call last):
File "C:\Scripts\2002\09\lambda01.py", line 139, in ?
quicksort(sorted,0,len(sorted)-1)
File "C:\Scripts\2002\09\lambda01.py", line 126, in <lambda>
q = lambda l,s,e:s<e and (lambda p:(q(l,s,p-1),q(l,p+1,e)))(partition(l,s,e))
File "C:\Scripts\2002\09\lambda01.py", line 119, in partition
pf1()
File "C:\Scripts\2002\09\lambda01.py", line 98, in pf1
while not done:
UnboundLocalError: local variable 'done' referenced before assignment


Come to think of it, it is pretty clear what happens: The variable done (and, btw, the variables bottom and top, too) cannot be referenced because they are - unlike list, for example - scalar variables and are outside the function scope. There is a very easy solution to this problem: just put all scalar variables in an array! We will use the following mapping

pivot  = locals
bottom = locals
top    = locals
done   = locals


and can now rewrite the code like this:

def partition(list, start, end):

locals = [list[end], # pivot
start-1,   # bottom
end,       # top
0          # done
]

while not locals:
while not locals:
locals = locals+1

if locals == locals:
locals = 1
break

if list[locals] > locals:
list[locals] = list[locals]
break

while not locals:
locals = locals-1

if locals == locals:
locals = 1
break

if list[locals] < locals:
list[locals] = list[locals]
break

list[locals] = locals
return locals


It sure looks ugly, but what the heck. Now we can finally move the two while loops to functions, as in:

def partition(list, start, end):

locals = [list[end], # pivot
start-1,   # bottom
end,       # top
0,         # done
0, 0]      # temp vars to be explained later

def temp1():
while not locals:
locals = locals+1

if locals == locals:
locals = 1
break

if list[locals] > locals:
list[locals] = list[locals]
break

def temp2():
while not locals:
locals = locals-1

if locals == locals:
locals = 1
break

if list[locals] < locals:
list[locals] = list[locals]
break

while not locals:
temp1()
temp2()

list[locals] = locals
return locals


Now, lets focus on temp1:

    def temp1():
while not locals:
locals = locals+1

if locals == locals:
locals = 1
break

if list[locals] > locals:
list[locals] = list[locals]
break


Take a look at that assignment of one list member to another, in the last if-statement. As we mentioned above, assignments are statements, not expressions, and cannot be used in lambda. And, we cannot just use the local variables creation trick we used above, because this time its one list member getting assigned to another list member. Fortunately, we can use the __setitem__ function:

>>> print [].__setitem__.__doc__
x.__setitem__(i, y) <==> x[i]=y


and write the assignment

list[bottom] = list[top]


like this

list.__setitem__(bottom,list[top])


And in much the same way for the locals=1 bit in the first if statement. A bit more difficult is the handling of the break statement. There just is no easy representation for that in lambda, but we can use local variables again. If you remember the line

  0, 0] # temps var to be explained later


from the above code, locals is just now comes in handy. We rewrite temp1 like this:

    def temp1():
locals.__setitem__(4,0)
while not locals and not locals:
locals = locals+1

if locals == locals:
locals.__setitem__(3,1)
locals.__setitem__(4,1)

elif list[locals] > locals:
list.__setitem__(locals,list[locals])
locals.__setitem__(4,1)


Note: If you understand what break does, you know why you have to change the second if-statement to an elif-statement.

The next step is to group the function groups in tuples:

        ...
if locals == locals:
(locals.__setitem__(3,1),locals.__setitem__(4,1))

elif list[locals] > locals:
(list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1))


and do the usual and-or-trick for the if-statements

    def temp1():
locals.__setitem__(4,0)
while not locals and not locals:
locals = locals+1
(locals == locals) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals] > locals \
and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1)))


Hehe. And we ain't even finished yet! but, the rest is a bit boring: change that assignment locals = locals+1 to __setitem__, and create a new tuple with both statements to form a single expression:

    def temp1():
locals.__setitem__(4,0)
while not locals and not locals:
(locals.__setitem__(1,locals+1),
(locals == locals) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals] > \
locals and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1))))


As mentioned in the section Using WHILE statements of my Stupid Lambda Tricks, you can rewrite

while expression():
function()


as

WHILE = lambda:e() and (f(),WHILE())


So lets try and see if that works for us. First, rewrite the code so that the while-structure is better visible:

    def temp1():
locals.__setitem__(4,0)

e = lambda: not locals and not locals
f = lambda: (locals.__setitem__(1,locals+1),
(locals == locals) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals] > \
locals and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1))))

while e():
f()


and then change while to a lambda expression

    def temp1():
locals.__setitem__(4,0)

e = lambda: not locals and not locals
f = lambda: (locals.__setitem__(1,locals+1),
(locals == locals) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals] > \
locals and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1))))
g = lambda: e() and (f(),g())

g()


It works! (I hope that you have tested all of the above yourself :). Now we can put e and f inside the definition of g:

    def temp1():
locals.__setitem__(4,0)
g = lambda: (not locals and not locals) and ((lambda:\
(locals.__setitem__(1,locals+1),(locals == locals) \
and (locals.__setitem__(3,1),locals.__setitem__(4,1)) or \
(list[locals] > locals and (list.__setitem__(locals,
list[locals]),locals.__setitem__(4,1)))))(),g())
g()


Nice. For the g= bit we use the second unused-as-of-yet local variable defined above, locals.

    def temp1():
locals.__setitem__(4,0)
locals = lambda: (not locals and not locals) and \
((lambda: (locals.__setitem__(1,locals+1),(locals == \
locals) and (locals.__setitem__(3,1),locals.__setitem__(4,1))\
or (list[locals] > locals and (list.__setitem__(locals,
list[locals]),locals.__setitem__(4,1)))))(),locals())
locals()


And rewrite the whole thing, using __setitem__ and a tuple again.

    def temp1():
(locals.__setitem__(4,0),
locals.__setitem__(5,lambda: (not locals and not locals)\
and ((lambda: (locals.__setitem__(1,locals+1),(locals ==\
locals) and (locals.__setitem__(3,1),locals.__setitem__(4,1))\
or (list[locals] > locals and (list.__setitem__(locals,\
list[locals]),locals.__setitem__(4,1)))))(),locals())),
locals())


Finally, we can make a lambda out of temp1, and we've come a long way:


temp1 = lambda: (locals.__setitem__(4,0),
locals.__setitem__(5,lambda: (not locals and not locals) and\
((lambda: (locals.__setitem__(1,locals+1),(locals == locals)\
and (locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals]\
> locals and (list.__setitem__(locals,list[locals]),\
locals.__setitem__(4,1)))))(),locals())),
locals())


After this, rewriting temp2() should be pretty straightforward:

    temp2 = lambda: (locals.__setitem__(4,0),
locals.__setitem__(5,lambda:(not locals and not locals) and \
(locals.__setitem__(2,locals-1),(locals == locals) and \
(locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals] \
< locals and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1))),locals())),
locals())


So, where are we at? Lets take a look at the whole partition function as we have it now:

def partition(list, start, end):

locals = [list[end],start-1,end,0,0,0]

temp1 = lambda: (locals.__setitem__(4,0),
locals.__setitem__(5,lambda: (not locals and not locals) and\
((lambda: (locals.__setitem__(1,locals+1),(locals == locals)\
and (locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals] >\
locals and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1)))))(),locals())),
locals())

temp2 = lambda: (locals.__setitem__(4,0),
locals.__setitem__(5,lambda:(not locals and not locals) and \
(locals.__setitem__(2,locals-1),(locals == locals) and \
(locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals] < \
locals and (list.__setitem__(locals,list[locals]),
locals.__setitem__(4,1))),locals())),
locals())

while not locals:
temp1()
temp2()

list[locals] = locals
return locals


This is a good time to rename all those long variable names to single chars, just for fun:

def partition(l, s, e):

o = [l[e],s-1,e,0,0,0]

temp1 = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and ((lambda: \
(o.__setitem__(1,o+1),(o == o) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o] > o and (l.__setitem__(o,\
l[o]),o.__setitem__(4,1)))))(),o())),
o())

temp2 = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and (o.__setitem__\
(2,o-1),(o == o) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o] < o and (l.__setitem__(o,l[o]),
o.__setitem__(4,1))),o())),o())

while not o:
temp1()
temp2()

l[o] = o
return o


The functions temp1 and temp2 are best put inside the local variables array, like this:

def partition(l, s, e):

o = [l[e],s-1,e,0,0,0,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and ((lambda:\
(o.__setitem__(1,o+1),(o == o) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o] > o and (l.__setitem__(o,\
l[o]),o.__setitem__(4,1)))))(),o())),
o()),lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and (o.__setitem__\
(2,o-1),(o == o) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o] < o and (l.__setitem__(o,l[o]),
o.__setitem__(4,1))),o())),o())]

while not o:
o()
o()

l[o] = o
return o


Modifying the while loop should be easy after all that:

    WHILE = lambda:not o and (o(),o(),WHILE())
WHILE()


and of course we'll put that function into the local variables, too, which gives us:

def partition(l, s, e):

o = [l[e],s-1,e,0,0,0,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and ((lambda: \
(o.__setitem__(1,o+1),(o == o) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o] > o and (l.__setitem__(o,\
l[o]),o.__setitem__(4,1)))))(),o())),
o()),lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and (o.__setitem__\
(2,o-1),(o == o) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o] < o and (l.__setitem__(o,l[o]),o.__setitem__(4,1))),o())),
o()),
lambda:not o and (o(),o(),o())]
o()
l[o] = o
return o


Next, group the final three statements together

    return (o(),l.__setitem__(o,o),o)[-1]


and put the whole thing inside a lambda expression, where o is a local variable:

def partition(l, s, e):

test = lambda o = [l[e],s-1,e,0,0,0,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and ((lambda:\
(o.__setitem__(1,o+1),(o == o) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o] > o and (l.__setitem__(o,\
l[o]),o.__setitem__(4,1)))))(),o())),
o()),lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and (o.__setitem__\
(2,o-1),(o == o) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o] < o and (l.__setitem__(o,l[o]),
o.__setitem__(4,1))),o())),o()),
lambda:not o and (o(),o(),o())]: (o(),\
l.__setitem__(o,o),o)[-1]

return test()


But, alas, this is too good to be true:

  File "C:\Scripts\2002\09\lambda01.py", line 429, in ?
quicksort(sorted,0,len(sorted)-1)
File "C:\Scripts\2002\09\lambda01.py", line 416, in <lambda>
q = lambda l,s,e:s<e and (lambda p:(q(l,s,p-1),q(l,p+1,e)))(partition(l,s,e))
File "C:\Scripts\2002\09\lambda01.py", line 414, in partition
return test()
File "C:\Scripts\2002\09\lambda01.py", line 407, in <lambda>
test = lambda o = [l[e],s-1,e,0,0,0,lambda: (o.__setitem__(4,0),
File "C:\Scripts\2002\09\lambda01.py", line 412, in <lambda>
lambda:not o and (o(),o(),o())]: (o(),l.__setitem__(o,o),o)[-1]
NameError: global name 'o' is not defined


The straightforward solution is to remove the lambda declarations from the array declaration, and use assignments instead:

def partition(l, s, e):

o = [l[e],s-1,e,0,0,0,0,0,0]

o = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and \
((lambda: (o.__setitem__(1,o+1),(o == o) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o] > o \
and (l.__setitem__(o,l[o]),o.__setitem__(4,1)))))(),
o())),o())
o = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and \
(o.__setitem__(2,o-1),(o == o) and (o.__setitem__\
(3,1),o.__setitem__(4,1)) or (l[o] < o and \
(l.__setitem__(o,l[o]),o.__setitem__(4,1))),o())),
o())
o = lambda:not o and (o(),o(),o())

return (o(),l.__setitem__(o,o),o)[-1]


then replace = with __setitem__ and group them together:

def partition(l, s, e):

o = [l[e],s-1,e,0,0,0,0,0,0]

return (o.__setitem__(6,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and \
((lambda: (o.__setitem__(1,o+1),(o == o) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o] > o\
and (l.__setitem__(o,l[o]),o.__setitem__(4,1)))))(),
o())),o())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and \
(o.__setitem__(2,o-1),(o == o) and (o.__setitem__\
(3,1),o.__setitem__(4,1)) or (l[o] < o and \
(l.__setitem__(o,l[o]),o.__setitem__(4,1))),o())),
o())),
o.__setitem__(8,lambda:not o and (o(),o(),o())),
o(),l.__setitem__(o,o),o)[-1]


Put that whole thing inside lambda

def partition(l, s, e):

temp = lambda o = [l[e],s-1,e,0,0,0,0,0,0]: (o.__setitem__\
(6,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and \
((lambda: (o.__setitem__(1,o+1),(o == o) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o] > \
o and (l.__setitem__(o,l[o]),o.__setitem__\
(4,1)))))(),o())),
o())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and \
(o.__setitem__(2,o-1),(o == o) and (o.__setitem__\
(3,1),o.__setitem__(4,1)) or (l[o] < o and \
(l.__setitem__(o,l[o]),o.__setitem__(4,1))),o())),
o())),
o.__setitem__(8,lambda:not o and (o(),o(),o())),
o(),l.__setitem__(o,o),o)[-1]

return temp()


and we are almost there:

partition = lambda l,s,e:(lambda o = [l[e],s-1,e,0,0,0,0,0,0]: \
(o.__setitem__(6,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and \
((lambda: (o.__setitem__(1,o+1),(o == o) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o] > o\
and (l.__setitem__(o,l[o]),o.__setitem__(4,1)))))(),
o())),o())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and \
(o.__setitem__(2,o-1),(o == o) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or \
(l[o] < o and (l.__setitem__(o,l[o]),
o.__setitem__(4,1))),o())),o())),
o.__setitem__(8,lambda:not o and (o(),o(),o())),
o(),l.__setitem__(o,o),o)[-1])()


At this point, the whole program reads:

partition = lambda l,s,e:(lambda o = [l[e],s-1,e,0,0,0,0,0,0]:\
(o.__setitem__(6,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o and not o) and \
((lambda: (o.__setitem__(1,o+1),(o == o) and\
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o] > o\
and (l.__setitem__(o,l[o]),o.__setitem__(4,1)))))(),
o())),o())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o and not o) and \
(o.__setitem__(2,o-1),(o == o) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or \
(l[o] < o and (l.__setitem__(o,l[o]),
o.__setitem__(4,1))),o())),o())),
o.__setitem__(8,lambda:not o and (o(),o(),o())),
o(),l.__setitem__(o,o),o)[-1])()

q = lambda l,s,e:s<e and (lambda p:(q(l,s,p-1),q(l,p+1,e)))(partition(l,s,e))

quicksort = q


and, as the partition function is used only once, it can be put inside the q function:

q = lambda l,s,e:s<e and (lambda p:(q(l,s,p-1),q(l,p+1,e)))((lambda o=[l[e],s-1,e,0,0,0,0,0,0]:\
(o.__setitem__(6,lambda: (o.__setitem__(4,0),o.__setitem__(5,lambda:(not o and not o)\
and ((lambda:(o.__setitem__(1,o+1),(o==o) and (o.__setitem__(3,1),o.__setitem__(4,\
1)) or (l[o]>o and (l.__setitem__(o,l[o]),o.__setitem__(4,1)))))(),o())),\
o())),o.__setitem__(7,lambda:(o.__setitem__(4,0),o.__setitem__(5,lambda:(not o and\
not o) and (o.__setitem__(2,o-1),(o==o) and (o.__setitem__(3,1),o.__setitem__\
(4,1)) or (l[o]<o and (l.__setitem__(o,l[o]),o.__setitem__(4,1))),o())),\
o())),o.__setitem__(8,lambda:not o and (o(),o(),o())),o(),l.__setitem__(\
o,o),o)[-1])())

quicksort = q


Thats' it! Now you know why lambda is an essential part of python! If you don't think this code works, or want to study it in more detail, here is an archive you can download a working copy here, complete with loads of sample steps (just look in the code).