Unsorting(randomizing) a sequence

[Cliff, or a close facsimile]

Pada 17 Aug 1999 20:54:58 -0400, Michael Haggerty bilang:
| 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.

I don't know how lists are implemented in Python, but if they're linked lists
instead of arrays, then deleting an element (once you've already found it)
should take constant time.  But then the append will be O(n).


| Each of those actions is O(N) so the whole loop is O(N**2).

Nope, it should still be O(n).


-- 
cliff crawford   http://www.people.cornell.edu/pages/cjc26/
            There are more stars in the sky than there are
-><-        grains of sand on all the beaches of the world.