quick sort

Python Algorithm

なんか以前も Haskell での quick sort について書いたような記憶があるけども、Python でもできたりするな。

def quicksort(xs):
    if len(xs) == 0: return []

    x = xs[0]
    return quicksort([y for y in xs[1:] if y < x]) \
           + [x] \
           + quicksort([y for y in xs[1:] if y >= x])

itertools.islice 使ったほうが効率良いかな。

from itertools import islice

def tail(xs):
    return islice(xs, 1, len(xs))

def quicksort(xs):
    if len(xs) == 0: return []

    x = xs[0]
    return quicksort([y for y in tail(xs) if y < x]) \
           + [x] \
           + quicksort([y for y in tail(xs) if y >= x])

まぁ、多少効率よくてもどうよ、という効率の悪さだと思うけど。