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
... TODO: add Explanation
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
return top
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
return top
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[0]
bottom = locals[1]
top = locals[2]
done = locals[3]
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[3]:
while not locals[3]:
locals[1] = locals[1]+1
if locals[1] == locals[2]:
locals[3] = 1
break
if list[locals[1]] > locals[0]:
list[locals[2]] = list[locals[1]]
break
while not locals[3]:
locals[2] = locals[2]-1
if locals[2] == locals[1]:
locals[3] = 1
break
if list[locals[2]] < locals[0]:
list[locals[1]] = list[locals[2]]
break
list[locals[2]] = locals[0]
return locals[2]
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[3]:
locals[1] = locals[1]+1
if locals[1] == locals[2]:
locals[3] = 1
break
if list[locals[1]] > locals[0]:
list[locals[2]] = list[locals[1]]
break
def temp2():
while not locals[3]:
locals[2] = locals[2]-1
if locals[2] == locals[1]:
locals[3] = 1
break
if list[locals[2]] < locals[0]:
list[locals[1]] = list[locals[2]]
break
while not locals[3]:
temp1()
temp2()
list[locals[2]] = locals[0]
return locals[2]
Now, lets focus on temp1:
def temp1():
while not locals[3]:
locals[1] = locals[1]+1
if locals[1] == locals[2]:
locals[3] = 1
break
if list[locals[1]] > locals[0]:
list[locals[2]] = list[locals[1]]
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[3]=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[4] is just now comes in handy. We rewrite temp1 like this:
def temp1():
locals.__setitem__(4,0)
while not locals[4] and not locals[3]:
locals[1] = locals[1]+1
if locals[1] == locals[2]:
locals.__setitem__(3,1)
locals.__setitem__(4,1)
elif list[locals[1]] > locals[0]:
list.__setitem__(locals[2],list[locals[1]])
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[1] == locals[2]:
(locals.__setitem__(3,1),locals.__setitem__(4,1))
elif list[locals[1]] > locals[0]:
(list.__setitem__(locals[2],list[locals[1]]),
locals.__setitem__(4,1))
and do the usual and-or-trick for the if-statements
def temp1():
locals.__setitem__(4,0)
while not locals[4] and not locals[3]:
locals[1] = locals[1]+1
(locals[1] == locals[2]) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals[1]] > locals[0] \
and (list.__setitem__(locals[2],list[locals[1]]),
locals.__setitem__(4,1)))
Hehe. And we ain't even finished yet! but, the rest is a bit boring: change that assignment locals[1] = locals[1]+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[4] and not locals[3]:
(locals.__setitem__(1,locals[1]+1),
(locals[1] == locals[2]) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals[1]] > \
locals[0] and (list.__setitem__(locals[2],list[locals[1]]),
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[4] and not locals[3]
f = lambda: (locals.__setitem__(1,locals[1]+1),
(locals[1] == locals[2]) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals[1]] > \
locals[0] and (list.__setitem__(locals[2],list[locals[1]]),
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[4] and not locals[3]
f = lambda: (locals.__setitem__(1,locals[1]+1),
(locals[1] == locals[2]) and (locals.__setitem__(3,1),
locals.__setitem__(4,1)) or (list[locals[1]] > \
locals[0] and (list.__setitem__(locals[2],list[locals[1]]),
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[4] and not locals[3]) and ((lambda:\
(locals.__setitem__(1,locals[1]+1),(locals[1] == locals[2]) \
and (locals.__setitem__(3,1),locals.__setitem__(4,1)) or \
(list[locals[1]] > locals[0] and (list.__setitem__(locals[2],
list[locals[1]]),locals.__setitem__(4,1)))))(),g())
g()
Nice. For the g=
bit we use the second unused-as-of-yet
local variable defined above, locals[5].
def temp1():
locals.__setitem__(4,0)
locals[5] = lambda: (not locals[4] and not locals[3]) and \
((lambda: (locals.__setitem__(1,locals[1]+1),(locals[1] == \
locals[2]) and (locals.__setitem__(3,1),locals.__setitem__(4,1))\
or (list[locals[1]] > locals[0] and (list.__setitem__(locals[2],
list[locals[1]]),locals.__setitem__(4,1)))))(),locals[5]())
locals[5]()
And rewrite the whole thing, using __setitem__ and a tuple again.
def temp1():
(locals.__setitem__(4,0),
locals.__setitem__(5,lambda: (not locals[4] and not locals[3])\
and ((lambda: (locals.__setitem__(1,locals[1]+1),(locals[1] ==\
locals[2]) and (locals.__setitem__(3,1),locals.__setitem__(4,1))\
or (list[locals[1]] > locals[0] and (list.__setitem__(locals[2],\
list[locals[1]]),locals.__setitem__(4,1)))))(),locals[5]())),
locals[5]())
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[4] and not locals[3]) and\
((lambda: (locals.__setitem__(1,locals[1]+1),(locals[1] == locals[2])\
and (locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals[1]]\
> locals[0] and (list.__setitem__(locals[2],list[locals[1]]),\
locals.__setitem__(4,1)))))(),locals[5]())),
locals[5]())
After this, rewriting temp2() should be pretty straightforward:
temp2 = lambda: (locals.__setitem__(4,0),
locals.__setitem__(5,lambda:(not locals[4] and not locals[3]) and \
(locals.__setitem__(2,locals[2]-1),(locals[2] == locals[1]) and \
(locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals[2]] \
< locals[0] and (list.__setitem__(locals[1],list[locals[2]]),
locals.__setitem__(4,1))),locals[5]())),
locals[5]())
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[4] and not locals[3]) and\
((lambda: (locals.__setitem__(1,locals[1]+1),(locals[1] == locals[2])\
and (locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals[1]] >\
locals[0] and (list.__setitem__(locals[2],list[locals[1]]),
locals.__setitem__(4,1)))))(),locals[5]())),
locals[5]())
temp2 = lambda: (locals.__setitem__(4,0),
locals.__setitem__(5,lambda:(not locals[4] and not locals[3]) and \
(locals.__setitem__(2,locals[2]-1),(locals[2] == locals[1]) and \
(locals.__setitem__(3,1),locals.__setitem__(4,1)) or (list[locals[2]] < \
locals[0] and (list.__setitem__(locals[1],list[locals[2]]),
locals.__setitem__(4,1))),locals[5]())),
locals[5]())
while not locals[3]:
temp1()
temp2()
list[locals[2]] = locals[0]
return locals[2]
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[4] and not o[3]) and ((lambda: \
(o.__setitem__(1,o[1]+1),(o[1] == o[2]) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o[1]] > o[0] and (l.__setitem__(o[2],\
l[o[1]]),o.__setitem__(4,1)))))(),o[5]())),
o[5]())
temp2 = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and (o.__setitem__\
(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o[2]] < o[0] and (l.__setitem__(o[1],l[o[2]]),
o.__setitem__(4,1))),o[5]())),o[5]())
while not o[3]:
temp1()
temp2()
l[o[2]] = o[0]
return o[2]
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[4] and not o[3]) and ((lambda:\
(o.__setitem__(1,o[1]+1),(o[1] == o[2]) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o[1]] > o[0] and (l.__setitem__(o[2],\
l[o[1]]),o.__setitem__(4,1)))))(),o[5]())),
o[5]()),lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and (o.__setitem__\
(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o[2]] < o[0] and (l.__setitem__(o[1],l[o[2]]),
o.__setitem__(4,1))),o[5]())),o[5]())]
while not o[3]:
o[6]()
o[7]()
l[o[2]] = o[0]
return o[2]
Modifying the while loop should be easy after all that:
WHILE = lambda:not o[3] and (o[6](),o[7](),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[4] and not o[3]) and ((lambda: \
(o.__setitem__(1,o[1]+1),(o[1] == o[2]) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o[1]] > o[0] and (l.__setitem__(o[2],\
l[o[1]]),o.__setitem__(4,1)))))(),o[5]())),
o[5]()),lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and (o.__setitem__\
(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o[2]] < o[0] and (l.__setitem__(o[1],l[o[2]]),o.__setitem__(4,1))),o[5]())),
o[5]()),
lambda:not o[3] and (o[6](),o[7](),o[8]())]
o[8]()
l[o[2]] = o[0]
return o[2]
Next, group the final three statements together
return (o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[4] and not o[3]) and ((lambda:\
(o.__setitem__(1,o[1]+1),(o[1] == o[2]) and (o.__setitem__(3,1),\
o.__setitem__(4,1)) or (l[o[1]] > o[0] and (l.__setitem__(o[2],\
l[o[1]]),o.__setitem__(4,1)))))(),o[5]())),
o[5]()),lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and (o.__setitem__\
(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__(3,1),o.__setitem__(4,1))\
or (l[o[2]] < o[0] and (l.__setitem__(o[1],l[o[2]]),
o.__setitem__(4,1))),o[5]())),o[5]()),
lambda:not o[3] and (o[6](),o[7](),o[8]())]: (o[8](),\
l.__setitem__(o[2],o[0]),o[2])[-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[3] and (o[6](),o[7](),o[8]())]: (o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[6] = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda: (not o[4] and not o[3]) and \
((lambda: (o.__setitem__(1,o[1]+1),(o[1] == o[2]) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o[1]] > o[0] \
and (l.__setitem__(o[2],l[o[1]]),o.__setitem__(4,1)))))(),
o[5]())),o[5]())
o[7] = lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and \
(o.__setitem__(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__\
(3,1),o.__setitem__(4,1)) or (l[o[2]] < o[0] and \
(l.__setitem__(o[1],l[o[2]]),o.__setitem__(4,1))),o[5]())),
o[5]())
o[8] = lambda:not o[3] and (o[6](),o[7](),o[8]())
return (o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[4] and not o[3]) and \
((lambda: (o.__setitem__(1,o[1]+1),(o[1] == o[2]) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o[1]] > o[0]\
and (l.__setitem__(o[2],l[o[1]]),o.__setitem__(4,1)))))(),
o[5]())),o[5]())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and \
(o.__setitem__(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__\
(3,1),o.__setitem__(4,1)) or (l[o[2]] < o[0] and \
(l.__setitem__(o[1],l[o[2]]),o.__setitem__(4,1))),o[5]())),
o[5]())),
o.__setitem__(8,lambda:not o[3] and (o[6](),o[7](),o[8]())),
o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[4] and not o[3]) and \
((lambda: (o.__setitem__(1,o[1]+1),(o[1] == o[2]) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o[1]] > \
o[0] and (l.__setitem__(o[2],l[o[1]]),o.__setitem__\
(4,1)))))(),o[5]())),
o[5]())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and \
(o.__setitem__(2,o[2]-1),(o[2] == o[1]) and (o.__setitem__\
(3,1),o.__setitem__(4,1)) or (l[o[2]] < o[0] and \
(l.__setitem__(o[1],l[o[2]]),o.__setitem__(4,1))),o[5]())),
o[5]())),
o.__setitem__(8,lambda:not o[3] and (o[6](),o[7](),o[8]())),
o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[4] and not o[3]) and \
((lambda: (o.__setitem__(1,o[1]+1),(o[1] == o[2]) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o[1]] > o[0]\
and (l.__setitem__(o[2],l[o[1]]),o.__setitem__(4,1)))))(),
o[5]())),o[5]())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and \
(o.__setitem__(2,o[2]-1),(o[2] == o[1]) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or \
(l[o[2]] < o[0] and (l.__setitem__(o[1],l[o[2]]),
o.__setitem__(4,1))),o[5]())),o[5]())),
o.__setitem__(8,lambda:not o[3] and (o[6](),o[7](),o[8]())),
o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[4] and not o[3]) and \
((lambda: (o.__setitem__(1,o[1]+1),(o[1] == o[2]) and\
(o.__setitem__(3,1),o.__setitem__(4,1)) or (l[o[1]] > o[0]\
and (l.__setitem__(o[2],l[o[1]]),o.__setitem__(4,1)))))(),
o[5]())),o[5]())),
o.__setitem__(7,lambda: (o.__setitem__(4,0),
o.__setitem__(5,lambda:(not o[4] and not o[3]) and \
(o.__setitem__(2,o[2]-1),(o[2] == o[1]) and \
(o.__setitem__(3,1),o.__setitem__(4,1)) or \
(l[o[2]] < o[0] and (l.__setitem__(o[1],l[o[2]]),
o.__setitem__(4,1))),o[5]())),o[5]())),
o.__setitem__(8,lambda:not o[3] and (o[6](),o[7](),o[8]())),
o[8](),l.__setitem__(o[2],o[0]),o[2])[-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[4] and not o[3])\
and ((lambda:(o.__setitem__(1,o[1]+1),(o[1]==o[2]) and (o.__setitem__(3,1),o.__setitem__(4,\
1)) or (l[o[1]]>o[0] and (l.__setitem__(o[2],l[o[1]]),o.__setitem__(4,1)))))(),o[5]())),\
o[5]())),o.__setitem__(7,lambda:(o.__setitem__(4,0),o.__setitem__(5,lambda:(not o[4] and\
not o[3]) and (o.__setitem__(2,o[2]-1),(o[2]==o[1]) and (o.__setitem__(3,1),o.__setitem__\
(4,1)) or (l[o[2]]<o[0] and (l.__setitem__(o[1],l[o[2]]),o.__setitem__(4,1))),o[5]())),\
o[5]())),o.__setitem__(8,lambda:not o[3] and (o[6](),o[7](),o[8]())),o[8](),l.__setitem__(\
o[2],o[0]),o[2])[-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).