Friday fun: Dropsort

By Filip Salo; published on January 26, 2007.

To celebrate the weekend, here's a python implementation of [a variant of] the dropsort algorithm:

def dropsort(seq):
    if not seq: return
    tail = [n for n in seq[1:] if n >= seq[0]]
    dropsort(tail)
    seq[1:] = tail

Test drive that puppy:

>>> numbers = random.sample(range(20), 20)
>>> numbers
[6, 13, 3, 9, 12, 4, 2, 8, 14, 10, 15, 0, 17, 7, 11, 5, 18, 16, 19, 1]
>>> dropsort(numbers)
>>> numbers
[6, 13, 14, 15, 17, 18, 19]

Yay!

Update: Extra! Extra! Non-in-place variant:

def dropsort(seq):
    if not seq: return []
    return [seq[0]] + dropsort([n for n in seq[1:] if n >= seq[0]])

There. I'm done for the day.