152 lines
1.8 KiB
Text
152 lines
1.8 KiB
Text
define limit = 10, iterations = 6
|
|
define iteration, size, middle, plusone
|
|
define point, top, high, low, pivot
|
|
|
|
dim list[limit]
|
|
dim stack[limit]
|
|
|
|
for iteration = 1 to iterations
|
|
|
|
gosub fill
|
|
gosub median
|
|
|
|
next iteration
|
|
|
|
end
|
|
|
|
sub fill
|
|
|
|
print "list: ",
|
|
|
|
erasearray list
|
|
|
|
let size = int(rnd * limit) + 1
|
|
|
|
if size <= 2 then
|
|
|
|
let size = 3
|
|
|
|
endif
|
|
|
|
for i = 0 to size - 1
|
|
|
|
let list[i] = rnd * 1000 + rnd
|
|
print list[i],
|
|
|
|
gosub printcomma
|
|
|
|
next i
|
|
|
|
return
|
|
|
|
sub median
|
|
|
|
gosub sort
|
|
|
|
print newline, "size: ", size, tab,
|
|
|
|
let middle = int((size - 1)/ 2)
|
|
print "middle: ", middle + 1, tab,
|
|
|
|
if size mod 2 then
|
|
|
|
print "median: ", list[middle]
|
|
|
|
else
|
|
|
|
let plusone = middle + 1
|
|
print "median: ", (list[middle] + list[plusone]) / 2
|
|
|
|
endif
|
|
|
|
print
|
|
|
|
return
|
|
|
|
sub sort
|
|
|
|
let low = 0
|
|
let high = size - 1
|
|
let top = -1
|
|
|
|
let top = top + 1
|
|
let stack[top] = low
|
|
let top = top + 1
|
|
let stack[top] = high
|
|
|
|
do
|
|
|
|
if top < 0 then
|
|
|
|
break
|
|
|
|
endif
|
|
|
|
let high = stack[top]
|
|
let top = top - 1
|
|
let low = stack[top]
|
|
let top = top - 1
|
|
|
|
let i = low - 1
|
|
|
|
for j = low to high - 1
|
|
|
|
if list[j] <= list[high] then
|
|
|
|
let i = i + 1
|
|
let t = list[i]
|
|
let list[i] = list[j]
|
|
let list[j] = t
|
|
|
|
endif
|
|
|
|
next j
|
|
|
|
let point = i + 1
|
|
let t = list[point]
|
|
let list[point] = list[high]
|
|
let list[high] = t
|
|
let pivot = i + 1
|
|
|
|
if pivot - 1 > low then
|
|
|
|
let top = top + 1
|
|
let stack[top] = low
|
|
let top = top + 1
|
|
let stack[top] = pivot - 1
|
|
|
|
endif
|
|
|
|
if pivot + 1 < high then
|
|
|
|
let top = top + 1
|
|
let stack[top] = pivot + 1
|
|
let top = top + 1
|
|
let stack[top] = high
|
|
|
|
endif
|
|
|
|
wait
|
|
|
|
loop top >= 0
|
|
|
|
print newline, "sorted: ",
|
|
|
|
for i = 0 to size - 1
|
|
|
|
print list[i],
|
|
gosub printcomma
|
|
|
|
next i
|
|
|
|
return
|
|
|
|
sub printcomma
|
|
|
|
if i < size - 1 then
|
|
|
|
print comma, " ",
|
|
|
|
endif
|
|
|
|
return
|