Problem Statement

Assume we have a set of items that can be sorted into an order by the user. The user is presented with pairs of items from the set in no order, the user states which item is less than, equal to, or greater than the other (with respect to their relative positions if fully ordered). Write a function that given items that the user can order, asks the user to give the result of comparing two items at a time and uses the comparison results to eventually return the items in order. Try and minimise the comparisons the user is asked for. Show on this page, the function ordering the colours of the rainbow: The correct ordering being: Note:

Let's start with the solution:

// Order by pair comparisons. Nigel Galloway: April 23rd., 2021
let clrs=let n=System.Random() in lN2p [|for g in 7..-1..2->n.Next(g)|] [|"Red";"Orange";"Yellow";"Green";"Blue";"Indigo";"Violet"|]
let rec fG n g=printfn "Is %s less than %s" n g; match System.Console.ReadLine() with "Yes"-> -1|"No"->1 |_->printfn "Enter Yes or No"; fG n g
let mutable z=0 in printfn "%A sorted to %A using %d questions" clrs (clrs|>Array.sortWith(fun n g->z<-z+1; fG n g)) z