Talk:Cycle sort

Pseudocode verification tool

This Python script verifies that the article's pseudocode both sorts correctly and does the theoretical minimum number of writes for all sort-distinguishable arrays (['b', 'b', 'c', 'a'] and [25, 25, 1003, -5] are indistinguishable to a sorter, so you need check only one of each kind) of a certain length. I've tested it with lengths 0 through 10. — Olathe (talk) 20:00, 4 October 2010 (UTC)

 import itertools
 
 def test(length=5):
   if length == 0:
     arr = []
     print arr,
     writes = cycleSort(arr)
     print writes
     if writes != 0:
       print "ERROR: cycleSort made excessive writes!"
     if len(arr) != 0:
       print "ERROR: cycleSort changed array length!"
     return
   # Horribly inefficient way to test all sorting-unique test vectors.
   for tup in itertools.product(range(length), repeat=length):
     arr = [x for x in tup]
     seq = True
     for i in range(max(arr)):
       if not (i in arr):
         seq = False
     if seq:
       bak = sorted(arr)
       neededWrites = length
       for i in range(len(arr)):
         if arr[i] == bak[i]:
           neededWrites -= 1
       print arr,
       writes = cycleSort(arr)
       print writes
       if len(arr) != length:
         print "ERROR: cycleSort changed array length!"
         return
       if arr != bak:
         print "ERROR: cycleSort didn't sort right!"
         return
       if writes != neededWrites:
         print "ERROR: cycleSort made excessive writes!"
         return