Talk:Cycle sort
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||
| ||||||||||||||||||||||||
Pseudocode verification tool
[edit]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