37 lines
1,005 B
Text
37 lines
1,005 B
Text
require "io2"
|
|
local fmt = require "fmt"
|
|
|
|
-- Inserts item x in list a, and keeps it sorted assuming a is already sorted.
|
|
-- If x is already in a, inserts it to the right of the rightmost x.
|
|
local function insort_right(a, x, q)
|
|
local lo = 1
|
|
local hi = #a + 1
|
|
local yn = "ynYN":split("")
|
|
while lo < hi do
|
|
local mid = (lo + hi) // 2
|
|
++q
|
|
local prompt = string.format("%2d: Is %6s less than %6s ? y/n: ", q, x, a[mid])
|
|
local less = string.lower(io.readOpt(prompt, yn)) == "y"
|
|
if less then
|
|
hi = mid
|
|
else
|
|
lo = mid + 1
|
|
end
|
|
end
|
|
a:insert(lo, x)
|
|
return q
|
|
end
|
|
|
|
local function order(items)
|
|
local ordered = {}
|
|
local q = 0
|
|
for items as item do
|
|
q = insort_right(ordered, item, q)
|
|
end
|
|
return ordered
|
|
end
|
|
|
|
local items = "violet red green indigo blue yellow orange":split(" ")
|
|
local ordered = order(items)
|
|
print("\nThe colors of the rainbow, in sorted order, are:")
|
|
fmt.lprint(ordered)
|