Velocity Reviews > Fun with fancy slicing

# Fun with fancy slicing

Ian McMeans
Guest
Posts: n/a

 10-05-2003
I've got to drop in my two cents
I wanted to see how clean I could make the algorithms look.

def quicksort(lst):
if len(lst) <= 1: return lst

left = [x for x in lst if x < lst[0]]
middle = [x for x in lst if x == lst[0]]
right = [x for x in lst if x > lst[0]]

return quicksort(left) + middle + quicksort(right)

>>> quicksort([random.randint(0, 20) for dummy in range(20)])

[0, 1, 2, 4, 4, 4, 4, 4, 6, 6, 8, 9, 12, 12, 13, 14, 14, 14, 16, 16]

Hopefully this is still nlogn

and then:

def primes():
p = {}
for cand in itertools.count(2):
if not [True for factor in p if not cand % factor]:
p[cand] = None
yield cand

list(itertools.islice(primes(), 0, 20))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

David Eppstein
Guest
Posts: n/a

 10-05-2003
In article <(E-Mail Removed) >,
http://www.velocityreviews.com/forums/(E-Mail Removed) (Ian McMeans) wrote:

> def quicksort(lst):
> if len(lst) <= 1: return lst
>
> left = [x for x in lst if x < lst[0]]
> middle = [x for x in lst if x == lst[0]]
> right = [x for x in lst if x > lst[0]]
>
> return quicksort(left) + middle + quicksort(right)
>
> >>> quicksort([random.randint(0, 20) for dummy in range(20)])

> [0, 1, 2, 4, 4, 4, 4, 4, 6, 6, 8, 9, 12, 12, 13, 14, 14, 14, 16, 16]
>
> Hopefully this is still nlogn

Well, for random inputs it is. If you want it to be O(n log n) even for
sorted inputs you could change it a little:

def quicksort(lst):
if len(lst) <= 1: return lst
pivot = lst[random.randrange(len(lst))]

left = [x for x in lst if x < pivot]
middle = [x for x in lst if x == pivot]
right = [x for x in lst if x > pivot]

return quicksort(left) + middle + quicksort(right)

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

Fernando Perez
Guest
Posts: n/a

 10-06-2003
Alex Martelli wrote:

> I would want the type of the rhs to be irrelevant, just as long as it's any
> iterable whatsoever, and bundle the 'excess items' into ONE specified
> kind of sequence. I also think it would be best for that one kind to be
> tuple, by analogy to argument passing: you can use any iterable as the
> actual argument 'expanded' by the *foo form, but whatever type foo
> is, if the formal argument is *bar then in the function bar is a TUPLE --
> period, simplest, no ifs, no buts. Maybe using a list instead might have
> been better, but tuple was chosen, and I think we should stick to that
> for unpacking, because the analogy with argument passing is a good
> part of the reason the *foo syntax appeals to me (maybe for the same
> reason we should at least for now forego the *foo appearing in any
> spot but the last... though that _would_ be a real real pity...).

Agreed: a single convention (and following tuples is a good one, if nothing
else b/c it's the existing one) is probably the sanest solution. I hadn't
thought of generators and arbitrary iterables, partly b/c I still use pretty
much 'naked' python 2.1 for everything.

Cheers,

f.