Fun with fancy slicing

[Alex Martelli]

David Eppstein wrote:
   ...
>> def quicksort(alist):
>>     head = alist[0]
>>     return quicksort([ x in alist[1:] if x<=head ]) + [
>>         head ] + quicksort([ x in alist[1:] if x>head ])
> 
> Well, except that it gets a syntax error.  And if you correct the syntax
> it gets an IndexError due to the lack of a base case for the recursion.

Right on both counts -- sorry.

> And if you correct that, it still doesn't work correctly for lists with
> repeated items.

Why not?  Having fixed the syntax and added the base-case, I see:

[alex at lancelot perex]$ python -i se.py
>>> import random
>>> x=4*range(5)
>>> random.shuffle(x)
>>> x
[4, 4, 3, 1, 1, 1, 1, 2, 0, 0, 3, 4, 3, 4, 2, 0, 3, 0, 2, 2]
>>> quicksort(x)
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]
>>>

So what am I missing?  Please show a case of "list with repeated
items" where the fixed quicksort "doesn't work correctly", thanks.

btw, my favourite fixed version is:

def quicksort(alist):
    try: head = alist[0]
    except IndexError: return alist
    return quicksort([ x for x in alist[1:] if x<=head ]) + [
        head ] + quicksort([ x for x in alist[1:] if x>head ])

but I do see that testing len(alist) is probably better.

How sweet it would be to be able to unpack by coding:
    head, *tail = alist
...


Alex