Unsorting(randomizing) a sequence

[Michael Haggerty]

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