0,]']╠>SО}WЪмuїПp8Їd%qy)6o;]иAіЖsОВТТТ■╟бVl├3 arr[j+1] then swap(j, j+1) selected = j coroutine.yield() end end end selected = -1 for i=0, 60 do coroutine.yield() end start() end) radix = coroutine.create(function() local radix = 4 local largest = n-1 local result = {} for i=1, n do result[i] = arr[i] end local exp = 1 while largest//exp > 0 do countingArr = countingSort(arr, exp, radix) for i=1, n do local t = arr[i] arr[i] = result[i] result[i] = t selected = i coroutine.yield() end for i=2, radix do countingArr[i] = countingArr[i]+countingArr[i-1] end for i=n, 1, -1 do local digit = math.floor(result[i]/exp)%radix local pos = countingArr[digit+1] arr[pos] = result[i] selected = pos countingArr[digit+1]=countingArr[digit+1]-1 coroutine.yield() end exp = exp*radix end selected = -1 for i=0, 60 do coroutine.yield() end start() end) function countingSort(arr, exp, radix) local countingArr = {} for i=1, radix do countingArr[i] = 0 end for i=1, n do countingArr[math.floor(arr[i]/exp)%radix+1]=countingArr[math.floor(arr[i]/exp)%radix+1]+1 selected = math.floor(arr[i]/exp)%radix+1 if i%2 == 0 then selected = math.floor(arr[i]/exp)%radix*(n/radix)+1 coroutine.yield() else selected = i coroutine.yield() end end return countingArr end selection = coroutine.create(function() local cur = n+1 local curIdx = 0 for i=1, n do cur = n+1 curIdx = 0 for j=i, n do if (j+i)%5 == 0 then selected = j coroutine.yield() end if arr[j] < cur then cur = arr[j] curIdx = j end end swap(i, curIdx) selected = curIdx coroutine.yield() end selected = -1 for i=0, 60 do coroutine.yield() end start() end) insertion = coroutine.create(function() for i=1, n do local pos = i-1 while pos >= 1 and arr[pos+1] < arr[pos] do swap(pos, pos+1) pos=pos-1 selected = math.max(pos, 1) coroutine.yield() end end selected = -1 for i=0, 60 do coroutine.yield() end start() end) comb = coroutine.create(function() local shrinkFactor = 1.3 local gap = n local swapped = true while gap > 1 or swapped do gap = gap // shrinkFactor if gap < 1 then gap = 1 end swapped = false for i=1, n-gap do selected = i+gap coroutine.yield() if arr[i] > arr[i + gap] then swap(i, i + gap) selected = i coroutine.yield() swapped = true end end end selected = -1 for i=0, 60 do coroutine.yield() end start() end) shell = coroutine.create(function() local shrinkFactor = 2.3; local gap = n while gap > 1 do gap = gap // shrinkFactor if gap < 1 then gap = 1 end for i=2, n do local pos = i-gap while pos >= 1 and arr[pos+gap] < arr[pos] do swap(pos, pos+gap) selected = pos+gap coroutine.yield() pos=pos-gap selected = math.max(pos, 1) coroutine.yield() end end end selected = -1 for i=0, 60 do coroutine.yield() end start() end) function swap(idx, idx1) arr[idx], arr[idx1] = arr[idx1], arr[idx] end routs = {{name="Bubble Sort (1/6)", co=bubble}, {name="Radix Sort (base 4) (2/6)", co=radix}, {name="Selection Sort (3/6)", co=selection}, {name="Insertion Sort (4/6)", co=insertion}, {name="Comb Sort (5/6)", co=comb}, {name="Shell Sort (6/6)", co=shell}} curSort = 0 curRout = nil done = false function start() arr = {} for i=1, n do arr[i] = i end curRout = {name="Shuffling...", co=coroutine.create(function() for i=1, n do swap(i, math.random(1, n)) selected = i coroutine.yield() end selected = -1 for i=0, 60 do coroutine.yield() end curSort = curSort + 1 if curSort > #routs then done = true else curRout = routs[curSort] end end)} end function BOOT() trace("start") start() end function TIC() if done then print("Done!", 0, 0, 13) else local ret = coroutine.resume(curRout.co) if ret == 1 then start() end cls(0) draw() end end function draw() for i=0, n-1 do rect(i*(w/n), h-arr[i+1]*(h/n), w/n, arr[i+1]*(h/n)+1, selected == i and 2 or 12) if selected == i then sfx(0, math.floor(arr[i]/n*60)+30, 3, 0, 5) end end if not done then print(curRout.name, 0, 0, 13) print("n = "..n, 0, 7, 13) end end