Unsorting(randomizing) a sequence

Michael Haggerty mhagger at blizzard.harvard.edu
Wed Aug 18 02:54:58 CEST 1999


mlh at idt.ntnu.no (Magnus L. Hetland) writes:

> result = []
> for i in range(len(l)):
>     element = random.choice(list)
>     l.remove(element)
>     result.append(element)
> 
> Probably not that quick, but...

Indeed not that quick.  This shuffle is O(N**2) because each time
through the loop it has to (1) search for the element by value and (2)
delete the element which involved shifting the rest of the list over
by one.  Each of those actions is O(N) so the whole loop is O(N**2).

Michael

-- 
Michael Haggerty
mhagger at blizzard.harvard.edu




More information about the Python-list mailing list