Re: random_sort (was Re: no response?)
- Posted by Jeffrey Fielding <JJProg at CYBERBURY.NET> Sep 19, 1998
- 487 views
Here is my solution to the random sort problem. Jeff Fielding JJProg at cyberbury.net -- A really slow random sort function -- I don't understand the rules perfectly, so tell me if it's ilegal function random_sort(sequence s) sequence sorted, checked object t integer a, b sorted = s checked = repeat(0,length(s)) for i = 1 to length(s) do checked[i] = i end for while length(checked) do a = rand(length(checked)) b = rand(length(checked)) a = checked[a] b = checked[b] if compare(sorted[a],sorted[b]) = 1 then t = sorted[a] sorted[a] = sorted[b] sorted[b] = t end if if get_key() != -1 then exit end if a = 1 checked = {} for i = 1 to length(sorted)-1 do if compare(sorted[i],sorted[i+1]) = 1 then a = 0 checked = checked & {i,i+1} end if end for if a = 1 then exit end if ? sorted end while return sorted end function function old_random_sort(sequence s) sequence sorted, checked object t integer a, b sorted = s checked = repeat(0,length(s)) while find(0,checked) do a = rand(length(s)) b = rand(length(s)) if checked[a] = 0 or checked[b] = 0 then if compare(sorted[a],sorted[b]) = 1 then t = sorted[a] sorted[a] = sorted[b] sorted[b] = t end if end if if get_key() != -1 then exit end if a = 1 checked = repeat(1,length(sorted)) for i = 1 to length(sorted)-1 do if compare(sorted[i],sorted[i+1]) = 1 then a = 0 checked[i] = 0 end if end for if a = 1 then exit end if ? sorted end while return sorted end function sequence s, tm atom t s = {} for i = 1 to 7 do s = s & rand(10) end for t = time() ? random_sort(s) t = time() - t tm = {t} t = time() ? old_random_sort(s) t = time() - t tm = tm & t printf(1,"%f %f",tm)