I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Order by pair comparisons

Order by pair comparisons
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

O(n log2n) sorts
Shell Sort

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:

```   violet red green indigo blue yellow orange
```

The correct ordering being:

```   red orange yellow green blue indigo violet
```

Note:

• Code inputs should not assume an ordering.
• The seven colours can form twenty-one different pairs.
• A routine that does not ask the user "too many" comparison questions should be used.

## 11l

`F user_cmp(String a, b)   R Int(input(‘IS #6 <, ==, or > #6  answer -1, 0 or 1:’.format(a, b))) V items = ‘violet red green indigo blue yellow orange’.split(‘ ’)V ans = sorted(items, key' cmp_to_key(user_cmp))print("\n"ans.join(‘ ’))`
Output:
```IS    red <, ==, or > violet  answer -1, 0 or 1:-1
IS  green <, ==, or >    red  answer -1, 0 or 1:1
IS  green <, ==, or > violet  answer -1, 0 or 1:-1
IS  green <, ==, or >    red  answer -1, 0 or 1:1
IS indigo <, ==, or >    red  answer -1, 0 or 1:1
IS indigo <, ==, or > violet  answer -1, 0 or 1:-1
IS indigo <, ==, or >  green  answer -1, 0 or 1:1
IS   blue <, ==, or >    red  answer -1, 0 or 1:1
IS   blue <, ==, or > violet  answer -1, 0 or 1:-1
IS   blue <, ==, or > indigo  answer -1, 0 or 1:-1
IS   blue <, ==, or >  green  answer -1, 0 or 1:1
IS yellow <, ==, or >    red  answer -1, 0 or 1:1
IS yellow <, ==, or > violet  answer -1, 0 or 1:-1
IS yellow <, ==, or > indigo  answer -1, 0 or 1:-1
IS yellow <, ==, or >   blue  answer -1, 0 or 1:-1
IS yellow <, ==, or >  green  answer -1, 0 or 1:-1
IS yellow <, ==, or >    red  answer -1, 0 or 1:1
IS orange <, ==, or >    red  answer -1, 0 or 1:1
IS orange <, ==, or > violet  answer -1, 0 or 1:-1
IS orange <, ==, or > indigo  answer -1, 0 or 1:-1
IS orange <, ==, or >   blue  answer -1, 0 or 1:-1
IS orange <, ==, or >  green  answer -1, 0 or 1:-1
IS orange <, ==, or > yellow  answer -1, 0 or 1:-1
IS orange <, ==, or >    red  answer -1, 0 or 1:1

red orange yellow green blue indigo violet
```

## Action!

`DEFINE PTR="CARD" PROC PrintArray(PTR ARRAY a BYTE size)  BYTE i   Put('[)  FOR i=0 TO size-1  DO    IF i>0 THEN Put(' ) FI    Print(a(i))  OD  Put(']) PutE()RETURN BYTE FUNC IsBefore(CHAR ARRAY a,b)  DEFINE NO_KEY="255"  DEFINE KEY_Y="43"  DEFINE KEY_N="35"  BYTE CH=\$02FC ;Internal hardware value for last key pressed  BYTE k   PrintF("Is %S before %S (y/n)? ",a,b)  CH=NO_KEY ;Flush the keyboard  DO    k=CH  UNTIL k=KEY_Y OR k=KEY_N  OD  CH=NO_KEY ;Flush the keyboard  IF k=KEY_Y THEN    PrintE("yes")    RETURN (1)  FI  PrintE("no")RETURN (0) PROC InteractiveInsertionSort(PTR ARRAY a BYTE size)  INT i,j  PTR value   FOR i=1 TO size-1  DO    value=a(i)    j=i-1    WHILE j>=0 AND IsBefore(value,a(j))=1    DO      a(j+1)=a(j)      j==-1    OD    a(j+1)=value  ODRETURN PROC Main()  DEFINE COUNT="7"  PTR ARRAY arr(COUNT)   arr(0)="violet" arr(1)="red"  arr(2)="green"  arr(3)="indigo"  arr(4)="blue"   arr(5)="yellow"  arr(6)="orange"   Print("Shuffled array: ")  PrintArray(arr,COUNT) PutE()   InteractiveInsertionSort(arr,COUNT)  PutE() Print("Sorted array: ")  PrintArray(arr,COUNT)RETURN`
Output:
```Shuffled array: [violet red green indigo blue yellow orange]

Is red before violet (y/n)? yes
Is green before violet (y/n)? yes
Is green before red (y/n)? no
Is indigo before violet (y/n)? yes
Is indigo before green (y/n)? no
Is blue before violet (y/n)? yes
Is blue before indigo (y/n)? yes
Is blue before green (y/n)? no
Is yellow before violet (y/n)? yes
Is yellow before indigo (y/n)? yes
Is yellow before blue (y/n)? yes
Is yellow before green (y/n)? yes
Is yellow before red (y/n)? no
Is orange before violet (y/n)? yes
Is orange before indigo (y/n)? yes
Is orange before blue (y/n)? yes
Is orange before green (y/n)? yes
Is orange before yellow (y/n)? yes
Is orange before red (y/n)? no

Sorted array: [red orange yellow green blue indigo violet]
```

## Arturo

`lst: ["violet" "red" "green" "indigo" "blue" "yellow" "orange"]count: 0 findSpot: function [l,e][    if empty? l -> return 0     loop.with:'i l 'item [        answer: input ~"Is |item| greater than |e| [y/n]? "        if answer="y" -> return i    ]    return dec size l] sortedLst: new [] loop lst 'element ->    insert 'sortedLst findSpot sortedLst element element print ""print ["sorted =>" sortedLst]`
Output:
```Is violet greater than red [y/n]? y
Is red greater than green [y/n]? y
Is green greater than indigo [y/n]? y
Is indigo greater than blue [y/n]? n
Is green greater than blue [y/n]? n
Is red greater than blue [y/n]? y
Is indigo greater than yellow [y/n]? n
Is green greater than yellow [y/n]? y
Is indigo greater than orange [y/n]? n
Is yellow greater than orange [y/n]? y

sorted => [indigo orange yellow green blue red violet]```

## AutoHotkey

`data := ["Violet", "Red", "Green", "Indigo", "Blue", "Yellow", "Orange"]result := [], num := 0, Questions :="" for i, Color1 in data{    found :=false    if !result.count(){        result.Push(Color1)        continue    }     for j, Color2 in result	{        if (color1 = color2)            continue        MsgBox, 262180,, % (Q := "Q" ++num " is " Color1 " > " Color2 "?")        ifMsgBox, Yes             Questions .= Q "`t`tYES`n"        else {            Questions .= Q "`t`tNO`n"            result.InsertAt(j, Color1)            found := true            break        }    }    if !found        result.Push(Color1)}for i, color in result    output .= color ", "MsgBox % Questions "`nSorted Output :`n" Trim(output, ", ")return`
Output:
```Q1 is Red > Violet?		NO
Q2 is Green > Red?		YES
Q3 is Green > Violet?		NO
Q4 is Indigo > Red?		YES
Q5 is Indigo > Green?		YES
Q6 is Indigo > Violet?		NO
Q7 is Blue > Red?		YES
Q8 is Blue > Green?		YES
Q9 is Blue > Indigo?		NO
Q10 is Yellow > Red?		YES
Q11 is Yellow > Green?		NO
Q12 is Orange > Red?		YES
Q13 is Orange > Yellow?		NO

Sorted Output :
Red, Orange, Yellow, Green, Blue, Indigo, Violet```

## C

Using qsort; not very efficient

`#include <stdio.h>#include <string.h>#include <stdlib.h> int interactiveCompare(const void *x1, const void *x2){  const char *s1 = *(const char * const *)x1;  const char *s2 = *(const char * const *)x2;  static int count = 0;  printf("(%d) Is %s <, ==, or > %s? Answer -1, 0, or 1: ", ++count, s1, s2);  int response;  scanf("%d", &response);  return response;} void printOrder(const char *items[], int len){  printf("{ ");  for (int i = 0; i < len; ++i) printf("%s ", items[i]);  printf("}\n");} int main(void){  const char *items[] =    {      "violet", "red", "green", "indigo", "blue", "yellow", "orange"    };   qsort(items, sizeof(items)/sizeof(*items), sizeof(*items), interactiveCompare);  printOrder(items, sizeof(items)/sizeof(*items));  return 0;}`
Output:
```(1) Is violet <, ==, or > red? Answer -1, 0, or 1: 1
(2) Is violet <, ==, or > green? Answer -1, 0, or 1: 1
(3) Is red <, ==, or > green? Answer -1, 0, or 1: -1
(4) Is violet <, ==, or > indigo? Answer -1, 0, or 1: 1
(5) Is green <, ==, or > indigo? Answer -1, 0, or 1: -1
(6) Is violet <, ==, or > blue? Answer -1, 0, or 1: 1
(7) Is indigo <, ==, or > blue? Answer -1, 0, or 1: 1
(8) Is green <, ==, or > blue? Answer -1, 0, or 1: -1
(9) Is violet <, ==, or > yellow? Answer -1, 0, or 1: 1
(10) Is indigo <, ==, or > yellow? Answer -1, 0, or 1: 1
(11) Is blue <, ==, or > yellow? Answer -1, 0, or 1: 1
(12) Is green <, ==, or > yellow? Answer -1, 0, or 1: 1
(13) Is red <, ==, or > yellow? Answer -1, 0, or 1: -1
(14) Is violet <, ==, or > orange? Answer -1, 0, or 1: 1
(15) Is indigo <, ==, or > orange? Answer -1, 0, or 1: 1
(16) Is blue <, ==, or > orange? Answer -1, 0, or 1: 1
(17) Is green <, ==, or > orange? Answer -1, 0, or 1: 1
(18) Is yellow <, ==, or > orange? Answer -1, 0, or 1: 1
(19) Is red <, ==, or > orange? Answer -1, 0, or 1: -1
{ red orange yellow green blue indigo violet }
```

## C++

### C++: Binary search insertion sort

`#include <algorithm>#include <iostream>#include <vector> using namespace std; bool InteractiveCompare(const string& s1, const string& s2){    if(s1 == s2) return false;  // don't ask to compare items that are the same    static int count = 0;    string response;    cout << "(" << ++count << ") Is " << s1 << " < " << s2 << "? ";    getline(cin, response);    return !response.empty() && response.front() == 'y';} void PrintOrder(const vector<string>& items){    cout << "{ ";    for(auto& item : items) cout << item << " ";    cout << "}\n";} int main(){    const vector<string> items    {        "violet", "red", "green", "indigo", "blue", "yellow", "orange"    };     vector<string> sortedItems;     // Use a binary insertion sort to order the items.  It should ask for    // close to the minimum number of questions required    for(auto& item : items)    {        cout << "Inserting '" << item << "' into ";        PrintOrder(sortedItems);        // lower_bound performs the binary search using InteractiveCompare to        // rank the items        auto spotToInsert = lower_bound(sortedItems.begin(),                                        sortedItems.end(), item, InteractiveCompare);        sortedItems.insert(spotToInsert, item);    }    PrintOrder(sortedItems);    return 0;}`
Output:
```Inserting 'violet' into { }
Inserting 'red' into { violet }
(1) Is violet < red? n
Inserting 'green' into { red violet }
(2) Is violet < green? n
(3) Is red < green? y
Inserting 'indigo' into { red green violet }
(4) Is green < indigo? y
(5) Is violet < indigo? n
Inserting 'blue' into { red green indigo violet }
(6) Is indigo < blue? n
(7) Is green < blue? y
Inserting 'yellow' into { red green blue indigo violet }
(8) Is blue < yellow? n
(9) Is green < yellow? n
(10) Is red < yellow? y
Inserting 'orange' into { red yellow green blue indigo violet }
(11) Is blue < orange? n
(12) Is yellow < orange? n
(13) Is red < orange? y
{ red orange yellow green blue indigo violet }
```

### C++: STL sort with custom comparator

`#include <algorithm>#include <iostream>#include <vector> using namespace std; bool InteractiveCompare(const string& s1, const string& s2){    if(s1 == s2) return false;  // don't ask to compare items that are the same    static int count = 0;    string response;    cout << "(" << ++count << ") Is " << s1 << " < " << s2 << "? ";    getline(cin, response);    return !response.empty() && response.front() == 'y';} void PrintOrder(const vector<string>& items){    cout << "{ ";    for(auto& item : items) cout << item << " ";    cout << "}\n";} int main(){    vector<string> items    {        "violet", "red", "green", "indigo", "blue", "yellow", "orange"    };     sort(items.begin(), items.end(), InteractiveCompare);    PrintOrder(items);    return 0;}`
Output:
```(1) Is indigo < violet? y
(2) Is orange < indigo? y
(3) Is orange < indigo? y
(4) Is red < indigo? y
(5) Is green < indigo? y
(6) Is yellow < indigo? y
(7) Is blue < indigo? y
(8) Is blue < indigo? y
(9) Is red < orange? y
(10) Is green < red? n
(11) Is green < orange? n
(12) Is yellow < green? y
(13) Is yellow < orange? n
(14) Is blue < green? n
{ red orange yellow green blue indigo violet }
```

## Commodore BASIC

`100 REM SORT BY COMPARISON110 DIM IN\$(6), OU\$(6)120 FOR I=0 TO 6:READ IN\$(I): NEXT I130 DATA VIOLET,RED,GREEN,INDIGO,BLUE,YELLOW,ORANGE140 OU\$(0)=IN\$(0):N=1150 FOR I=1 TO 6160 : IN\$=IN\$(I)180 : GOSUB 390190 : FOR J=0 TO N-1200 :  OU\$ = OU\$(J)210 :  GOSUB 340220 :  IF R>=0 THEN 280230 :  FOR K=N TO J+1 STEP -1240 :   OU\$(K) = OU\$(K-1)250 :  NEXT K260 :  OU\$(J) = IN\$270 :  GOTO 300280 : NEXT J290 : OU\$(N) = IN\$300 : N=N+1310 NEXT I320 GOSUB 390330 END340 PRINT "IS "IN\$" < "OU\$"? (Y/N)";350 GET K\$: IF K\$<>"Y" AND K\$<>"N" THEN 350360 PRINT K\$370 R = K\$="Y"380 RETURN390 PRINT "(";400 IF N=1 THEN 420410 FOR Q=0 TO N-2:PRINT OU\$(Q)",";:NEXT Q420 PRINT OU\$(N-1)")"430 RETURN`
Output:
```IS RED < VIOLET? (Y/N)Y
IS GREEN < RED? (Y/N)N
IS GREEN < VIOLET? (Y/N)Y
IS INDIGO < RED? (Y/N)N
IS INDIGO < GREEN? (Y/N)N
IS INDIGO < VIOLET? (Y/N)Y
IS BLUE < RED? (Y/N)N
IS BLUE < GREEN? (Y/N)N
IS BLUE < INDIGO? (Y/N)Y
IS YELLOW < RED? (Y/N)N
IS YELLOW < GREEN? (Y/N)Y
IS ORANGE < RED? (Y/N)N
IS ORANGE < YELLOW? (Y/N)Y
(RED,ORANGE,YELLOW,GREEN,BLUE,INDIGO,VIOLET)```

## F#

` // Order by pair comparisons. Nigel Galloway: April 23rd., 2021let 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 glet 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 `
Output:

Possible interaction:

```Is Indigo less than Orange
Yes
Is Blue less than Orange
Yes
Is Blue less than Indigo
No
Is Yellow less than Orange
Yes
Is Yellow less than Blue
No
Is Red less than Orange
Yes
Is Red less than Yellow
Yes
Is Red less than Blue
Yes
Is Red less than Indigo
Yes
Is Green less than Orange
Yes
Is Green less than Yellow
Yes
Is Green less than Blue
Yes
Is Green less than Indigo
Yes
Is Green less than Red
No
Is Violet less than Orange
Yes
Is Violet less than Yellow
Yes
Is Violet less than Blue
Yes
Is Violet less than Indigo
Yes
Is Violet less than Green
Yes
Is Violet less than Red
Yes
[|"Orange"; "Indigo"; "Blue"; "Yellow"; "Red"; "Green"; "Violet"|] sorted to [|"Violet"; "Red"; "Green"; "Indigo"; "Blue"; "Yellow"; "Orange"|] using 20 questions
```

## Factor

Asking the user for an ordering specifier inside a custom comparator:

Works with: Factor version 0.99 2021-02-05
`USING: formatting io kernel math.order prettyprint qw sorting ; qw{ violet red green indigo blue yellow orange }[ "Is %s > %s? (y/n) " printf readln "y" = +gt+ +lt+ ? ] sort .`
Output:
```Is violet > red? (y/n) y
Is green > indigo? (y/n) n
Is blue > yellow? (y/n) y
Is red > green? (y/n) n
Is violet > green? (y/n) y
Is violet > indigo? (y/n) y
Is yellow > orange? (y/n) y
Is red > orange? (y/n) n
Is green > orange? (y/n) y
Is green > yellow? (y/n) y
Is green > blue? (y/n) n
Is indigo > blue? (y/n) y
{ "red" "orange" "yellow" "green" "blue" "indigo" "violet" }
```

## FreeBASIC

Translation of: Commodore BASIC
` Dim Shared As Byte r, n = 1Dim Shared As String IN1, OU1Dim Shared As String IN(6), OU(6)Dim As Byte i, j, kFor i = 0 To 6 : Read IN(i) : Next iData "violet", "red", "green", "indigo", "blue", "yellow", "orange"OU(0) = IN(0) Sub PrintOrder     Print : Print "{";    If n = 1 Then Print OU(n-1);")" : Exit Sub    For q As Byte = 0 To n-2        Print OU(q);", ";    Next q            Print OU(n-1);"}"End Sub Sub InteractiveCompare    Dim As String*1 T    Print "Es "; IN1; " < "; OU1; "? (S/N) ";    Do: T = Inkey\$: Loop Until T <> ""    If Instr("snSN", T) Then Print Ucase(T)    r = T = "S"End Sub For i = 1 To 6    IN1 = IN(i)     For j = 0 To n-1        OU1 = OU(j)        InteractiveCompare        If r < 0 Then            For k = n To j+1 Step -1                OU(k) = OU(k-1)            Next k            OU(j) = IN1            n += 1            Exit For, For        End If    Next j    OU(n) = IN1    n += 1Next iPrintOrderSleep `

## Go

### Go: Binary search insertion sort

`package main import (    "fmt"    "sort"    "strings") var count int = 0 func interactiveCompare(s1, s2 string) bool {    count++    fmt.Printf("(%d) Is %s < %s? ", count, s1, s2)    var response string    _, err := fmt.Scanln(&response)    return err == nil && strings.HasPrefix(response, "y")} func main() {    items := []string{"violet", "red", "green", "indigo", "blue", "yellow", "orange"}     var sortedItems []string     // Use a binary insertion sort to order the items.  It should ask for    // close to the minimum number of questions required    for _, item := range items {        fmt.Printf("Inserting '%s' into %s\n", item, sortedItems)        // sort.Search performs the binary search using interactiveCompare to        // rank the items        spotToInsert := sort.Search(len(sortedItems), func(i int) bool {            return interactiveCompare(item, sortedItems[i])        })        sortedItems = append(sortedItems[:spotToInsert],                             append([]string{item}, sortedItems[spotToInsert:]...)...)    }    fmt.Println(sortedItems)}`
Output:
```Inserting 'violet' into []
Inserting 'red' into [violet]
(1) Is red < violet? y
Inserting 'green' into [red violet]
(2) Is green < violet? y
(3) Is green < red? n
Inserting 'indigo' into [red green violet]
(4) Is indigo < green? n
(5) Is indigo < violet? y
Inserting 'blue' into [red green indigo violet]
(6) Is blue < indigo? y
(7) Is blue < green? n
Inserting 'yellow' into [red green blue indigo violet]
(8) Is yellow < blue? y
(9) Is yellow < green? y
(10) Is yellow < red? n
Inserting 'orange' into [red yellow green blue indigo violet]
(11) Is orange < blue? y
(12) Is orange < yellow? y
(13) Is orange < red? n
[red orange yellow green blue indigo violet]
```

### Go: Standard sort with custom comparator

`package main import (    "fmt"    "sort"    "strings") var count int = 0 type sortable []stringfunc (s sortable) Len() int      { return len(s) }func (s sortable) Swap(i, j int) { s[i], s[j] = s[j], s[i] }func (s sortable) Less(i, j int) bool {    s1, s2 := s[i], s[j]    count++    fmt.Printf("(%d) Is %s < %s? ", count, s1, s2)    var response string    _, err := fmt.Scanln(&response)    return err == nil && strings.HasPrefix(response, "y")} func main() {    items := sortable{"violet", "red", "green", "indigo", "blue", "yellow", "orange"}    sort.Sort(items)    fmt.Println(items)}`
Output:
```(1) Is orange < violet? y
(2) Is red < orange? y
(3) Is green < orange? n
(4) Is indigo < green? n
(5) Is blue < indigo? y
(6) Is blue < green? n
(7) Is yellow < indigo? y
(8) Is yellow < blue? y
(9) Is yellow < green? y
(10) Is yellow < orange? n
(11) Is violet < indigo? n
[red orange yellow green blue indigo violet]
```

Injection of interaction with user is not straight-forward in pure functional language. In Haskell we use monads in order to abstract the computation flow and side effects. Fortunately the monadlist library [[1]] contains monadic variants of most popular list operations so that it becomes easy to implement our favorite sorting algorithms.

`import Control.Monadimport Control.Monad.ListM (sortByM, insertByM, partitionM, minimumByM)import Data.Bool (bool)import Data.Monoidimport Data.List --------------------------------------------------------------------------------isortM, msortM, tsortM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a] -- merge sort from the Control.Monad.ListM librarymsortM = sortByM -- insertion sortisortM cmp = foldM (flip (insertByM cmp)) [] -- tree sort aka qsort (which is not)tsortM cmp = go  where    go [] = pure []    go (h:t) = do (l, g) <- partitionM (fmap (LT /=) . cmp h) t                  go l <+> pure [h] <+> go g    (<+>) = liftM2 (++)`

Now we can sort lists with effects. For example, we may count number of comparisons, using writer monad:

```*Main> let countComparisons cmp a b = (Sum 1, a `cmp` b)
*Main> msortM (countComparisons compare) [2,6,3,5,9,1,5]
(Sum {getSum = 15},[1,2,3,5,5,6,9])

*Main> isortM (countComparisons compare) [2,6,3,5,9,1,5]
(Sum {getSum = 15},[1,2,3,5,5,6,9])

*Main> tsortM (countComparisons compare) [2,6,3,5,9,1,5]
(Sum {getSum = 13},[1,2,3,5,5,6,9])```

Or use a "database" as a reference for sorting, using reader monad

```let fromList a b l = elemIndex a l `compare` elemIndex b l
*Main> msortM fromList [2,1,3,2,4,4,5,11,2,3,2,3] [1..]
[1,2,2,2,2,3,3,3,4,4,5,11]```

Or even generate all possible permutations of a list making comparisons ambiguous:

```*Main> isortM (\_ _ -> [LT, GT]) [1,2,3]
[[1,2,3],[1,3,2],[3,1,2],[2,1,3],[2,3,1],[3,2,1]]```

`ask a b = do  putStr \$ show a ++ " ≤ " ++ show b ++ " ? [y/n]  "  bool GT LT . ("y" ==) <\$> getLine colors = ["Violet", "Red", "Green", "Indigo", "Blue", "Yellow", "Orange"]`
```*Main> isortM ask colors
"Red" ≤ "Violet" ? [y/n]  y
"Green" ≤ "Red" ? [y/n]  n
"Green" ≤ "Violet" ? [y/n]  y
"Indigo" ≤ "Red" ? [y/n]  n
"Indigo" ≤ "Green" ? [y/n]  n
"Indigo" ≤ "Violet" ? [y/n]  y
"Blue" ≤ "Red" ? [y/n]  n
"Blue" ≤ "Green" ? [y/n]  n
"Blue" ≤ "Indigo" ? [y/n]  y
"Yellow" ≤ "Red" ? [y/n]  n
"Yellow" ≤ "Green" ? [y/n]  y
"Orange" ≤ "Red" ? [y/n]  n
"Orange" ≤ "Yellow" ? [y/n]  y
["Red","Orange","Yellow","Green","Blue","Indigo","Violet"]

"Violet" ≤ "Red" ? [y/n]  n
"Red" ≤ "Green" ? [y/n]  y
"Green" ≤ "Indigo" ? [y/n]  y
"Indigo" ≤ "Blue" ? [y/n]  n
"Blue" ≤ "Yellow" ? [y/n]  n
"Yellow" ≤ "Orange" ? [y/n]  n
"Red" ≤ "Green" ? [y/n]  y
"Violet" ≤ "Green" ? [y/n]  n
"Violet" ≤ "Indigo" ? [y/n]  n
"Red" ≤ "Orange" ? [y/n]  y
"Green" ≤ "Orange" ? [y/n]  n
"Green" ≤ "Yellow" ? [y/n]  n
"Green" ≤ "Blue" ? [y/n]  y
"Indigo" ≤ "Blue" ? [y/n]  n
["Red","Orange","Yellow","Green","Blue","Indigo","Violet"]

"Violet" ≤ "Red" ? [y/n]  n
"Violet" ≤ "Green" ? [y/n]  n
"Violet" ≤ "Indigo" ? [y/n]  n
"Violet" ≤ "Blue" ? [y/n]  n
"Violet" ≤ "Yellow" ? [y/n]  n
"Violet" ≤ "Orange" ? [y/n]  n
"Red" ≤ "Green" ? [y/n]  y
"Red" ≤ "Indigo" ? [y/n]  y
"Red" ≤ "Blue" ? [y/n]  y
"Red" ≤ "Yellow" ? [y/n]  y
"Red" ≤ "Orange" ? [y/n]  y
"Green" ≤ "Indigo" ? [y/n]  y
"Green" ≤ "Blue" ? [y/n]  y
"Green" ≤ "Yellow" ? [y/n]  n
"Green" ≤ "Orange" ? [y/n]  n
"Yellow" ≤ "Orange" ? [y/n]  n
"Indigo" ≤ "Blue" ? [y/n]  n
["Red","Orange","Yellow","Green","Blue","Indigo","Violet"]```

It seems that insertion sort with 13 comparisons is the best one, and tree sort which needed 17 questions is the worst. But efficiency of sorting depends on the order of given list. Simple statistics could be made to compare these three methods for all possible permutations of seven elements.

`test method = do  mapM_ showHist \$ hist res  putStrLn \$ "Median number of comparisons: " ++ show (median res)  putStrLn \$ "Mean number of comparisons: " ++ show (mean res)  where    res = getSum . fst . method cmp <\$> permutations [1..7]    cmp a b = (Sum 1, compare a b)    median lst = sort lst !! (length lst `div` 2)    mean lst = sum (fromIntegral <\$> lst) / genericLength lst    hist lst = (\x -> (head x, length x)) <\$> group (sort lst)    showHist (n, l) = putStrLn line      where        line = show n ++ "\t" ++ bar ++ " " ++ show perc ++ "%"        bar = replicate (max perc 1) '*'        perc = (100 * l) `div` product [1..7]`

Comparing these three methods gives that for random inputs tree sort is the best choice.

```*Main> test msortM
6	* 0%
7	* 0%
8	* 0%
9	* 0%
10	* 1%
11	*** 3%
12	******* 7%
13	******** 8%
14	**************** 16%
15	************************ 24%
16	************************ 24%
17	************ 12%
Median number of comparisons: 15
Mean number of comparisons: 14.693055555555556

*Main> test isortM
6	* 0%
7	* 0%
8	* 0%
9	* 1%
10	*** 3%
11	***** 5%
12	******** 8%
13	********** 10%
14	************ 12%
15	************* 13%
16	************* 13%
17	*********** 11%
18	******** 8%
19	***** 5%
20	*** 3%
21	* 1%
Median number of comparisons: 15
Mean number of comparisons: 14.907142857142857

*Main> test tsortM
10	* 1%
11	******************** 20%
12	******************** 20%
13	***************** 17%
14	******** 8%
15	************* 13%
16	***** 5%
17	****** 6%
18	** 2%
19	* 1%
20	* 0%
21	* 1%
Median number of comparisons: 13
Mean number of comparisons: 13.485714285714286```

## Java

### Java: Binary search insertion sort

`import java.util.*; public class SortComp1 {    public static void main(String[] args) {        List<String> items = Arrays.asList("violet", "red", "green", "indigo", "blue", "yellow", "orange");        List<String> sortedItems = new ArrayList<>();        Comparator<String> interactiveCompare = new Comparator<String>() {                int count = 0;                Scanner s = new Scanner(System.in);                public int compare(String s1, String s2) {                    System.out.printf("(%d) Is %s <, =, or > %s. Answer -1, 0, or 1: ", ++count, s1, s2);                    return s.nextInt();                }            };        for (String item : items) {            System.out.printf("Inserting '%s' into %s\n", item, sortedItems);            int spotToInsert = Collections.binarySearch(sortedItems, item, interactiveCompare);            // when item does not equal an element in sortedItems,            // it returns bitwise complement of insertion point            if (spotToInsert < 0) spotToInsert = ~spotToInsert;            sortedItems.add(spotToInsert, item);        }        System.out.println(sortedItems);    }}`
Output:
```Inserting 'violet' into []
Inserting 'red' into [violet]
(1) Is violet <, =, or > red. Answer -1, 0, or 1: 1
Inserting 'green' into [red, violet]
(2) Is red <, =, or > green. Answer -1, 0, or 1: -1
(3) Is violet <, =, or > green. Answer -1, 0, or 1: 1
Inserting 'indigo' into [red, green, violet]
(4) Is green <, =, or > indigo. Answer -1, 0, or 1: -1
(5) Is violet <, =, or > indigo. Answer -1, 0, or 1: 1
Inserting 'blue' into [red, green, indigo, violet]
(6) Is green <, =, or > blue. Answer -1, 0, or 1: -1
(7) Is indigo <, =, or > blue. Answer -1, 0, or 1: 1
Inserting 'yellow' into [red, green, blue, indigo, violet]
(8) Is blue <, =, or > yellow. Answer -1, 0, or 1: 1
(9) Is red <, =, or > yellow. Answer -1, 0, or 1: -1
(10) Is green <, =, or > yellow. Answer -1, 0, or 1: 1
Inserting 'orange' into [red, yellow, green, blue, indigo, violet]
(11) Is green <, =, or > orange. Answer -1, 0, or 1: 1
(12) Is red <, =, or > orange. Answer -1, 0, or 1: -1
(13) Is yellow <, =, or > orange. Answer -1, 0, or 1: 1
[red, orange, yellow, green, blue, indigo, violet]
```

### Java: Standard sort with custom comparator

`import java.util.*; public class OrderByPair {    public static void main(String[] args) {        List<String> items = Arrays.asList("violet", "red", "green", "indigo", "blue", "yellow", "orange");        Collections.sort(items, new Comparator<String>() {                int count = 0;                Scanner s = new Scanner(System.in);                public int compare(String s1, String s2) {                    System.out.printf("(%d) Is %s <, =, or > %s. Answer -1, 0, or 1: ", ++count, s1, s2);                    return s.nextInt();                }            });        System.out.println(items);    }}`
Output:
```(1) Is red <, =, or > violet. Answer -1, 0, or 1: -1
(2) Is green <, =, or > red. Answer -1, 0, or 1: 1
(3) Is green <, =, or > violet. Answer -1, 0, or 1: -1
(4) Is green <, =, or > red. Answer -1, 0, or 1: 1
(5) Is indigo <, =, or > green. Answer -1, 0, or 1: 1
(6) Is indigo <, =, or > violet. Answer -1, 0, or 1: -1
(7) Is blue <, =, or > indigo. Answer -1, 0, or 1: -1
(8) Is blue <, =, or > green. Answer -1, 0, or 1: 1
(9) Is yellow <, =, or > blue. Answer -1, 0, or 1: -1
(10) Is yellow <, =, or > green. Answer -1, 0, or 1: -1
(11) Is yellow <, =, or > red. Answer -1, 0, or 1: 1
(12) Is orange <, =, or > blue. Answer -1, 0, or 1: -1
(13) Is orange <, =, or > yellow. Answer -1, 0, or 1: 1
(14) Is orange <, =, or > green. Answer -1, 0, or 1: 1
[red, yellow, green, orange, blue, indigo, violet]
```

## jq

Translation of: Wren
Works with: jq

Works with gojq, the Go implementation of jq

In order for a jq program to interact with a user, prompts must be directed to stderr, which currently means that the prompt string will be printed with quotation marks.

`def inputOption(\$prompt; \$options):  def r:    \$prompt | stderr    | input as \$in      | if \$in|test(\$options) then \$in else r end;  r; # Inserts item \$x in the array input, which is kept sorted as per user input# assuming it is already sorted.  \$q is the prompt number.# Input: [\$q; \$a]# Output: [\$qPrime, \$aPrime] def insortRight(\$x):  . as [\$q, \$a]  | { lo: 0, hi: (\$a|length), \$q }  | until( .lo >= .hi;         ( ((.lo + .hi)/2)|floor) as \$mid        | .q += 1        | "\(.q): Is \(\$x) less than \(\$a[\$mid])? y/n: " as \$prompt        | (inputOption(\$prompt; "[yn]") == "y") as \$less         | if (\$less) then .hi = \$mid          else .lo = \$mid + 1          end)    # insert at position .lo   | [ .q, (\$a[: .lo] + [x] + \$a[.lo :]) ]; def order:  reduce .[] as \$item ( [0, []]; insortRight(\$item) )  | .[1]; ["violet red green indigo blue yellow orange"|splits(" ")]| order as \$ordered| ("\nThe colors of the rainbow, in sorted order, are:",    \$ordered )`

Recommended Invocation Options: -nRrc

Sample Transcript

```"1: Is red less than violet? y/n: "y
y
"2: Is green less than violet? y/n: "y
y
"3: Is green less than red? y/n: "n
n
"4: Is indigo less than green? y/n: "n
n
"5: Is indigo less than violet? y/n: "y
y
"6: Is blue less than indigo? y/n: "y
y
"7: Is blue less than green? y/n: "n
n
"8: Is yellow less than blue? y/n: "y
y
"9: Is yellow less than green? y/n: "y
y
"10: Is yellow less than red? y/n: "n
n
"11: Is orange less than blue? y/n: "y
y
"12: Is orange less than yellow? y/n: "y
y
"13: Is orange less than red? y/n: "n
n

The colors of the rainbow, in sorted order, are:
["red","orange","yellow","green","blue","indigo","violet"]
```

## Julia

`const nrequests = [0]const ordering = Dict("violet" => 7, "red" => 1, "green" => 4, "indigo" => 6, "blue" => 5,                      "yellow" => 3, "orange" => 2) function tellmeifgt(x, y)    nrequests[1] += 1    while true        print("Is \$x greater than \$y?  (Y/N) =>  ")        s = strip(readline())        if length(s) > 0            (s[1] == 'Y' || s[1] == 'y') && return true            (s[1] == 'N' || s[1] == 'n') && return false        end    endend function orderbypair!(a::Vector)    incr = div(length(a), 2)    while incr > 0        for i in incr+1:length(a)            j = i            tmp = a[i]            while j > incr && tellmeifgt(a[j - incr], tmp)                a[j] = a[j-incr]                j -= incr            end            a[j] = tmp        end        if incr == 2            incr = 1        else            incr = floor(Int, incr * 5.0 / 11)        end    end    return aend const words = String.(split("violet red green indigo blue yellow orange", r"\s+"))println("Unsorted: \$words")println("Sorted: \$(orderbypair!(words)). Total requests: \$(nrequests[1]).") `
Output:
```Is violet greater than indigo?  (Y/N) =>  y
Is red greater than blue?  (Y/N) =>  n
Is green greater than yellow?  (Y/N) =>  y
Is violet greater than orange?  (Y/N) =>  y
Is indigo greater than orange?  (Y/N) =>  y
Is orange greater than red?  (Y/N) =>  y
Is orange greater than yellow?  (Y/N) =>  n
Is yellow greater than indigo?  (Y/N) =>  n
Is indigo greater than blue?  (Y/N) =>  y
Is yellow greater than blue?  (Y/N) =>  n
Is indigo greater than green?  (Y/N) =>  y
Is blue greater than green?  (Y/N) =>  y
Is yellow greater than green?  (Y/N) =>  n
Is indigo greater than violet?  (Y/N) =>  n
Sorted: ["red", "orange", "yellow", "green", "blue", "indigo", "violet"]. Total requests: 14.
```

## Mathematica / Wolfram Language

`ClearAll[HumanOrderCheck]HumanOrderCheck[opt1_,opt2_]:=ChoiceDialog[[email protected]{"Is {",opt1,", ", opt2, "} ordered?"},{"Yes"->True,"No"->False}]Sort[{"violet","red","green","indigo","blue","yellow","orange"},HumanOrderCheck]`
Output:

After some Yes/No clicks you should get:

`{"red", "orange", "yellow", "green", "blue", "indigo", "violet"}`

## Nim

Using a list filled by binary insertion and a custom comparison function.

`import algorithm, strformat, strutils let list = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"] var count = 0 proc comp(x, y: string): int =  if x == y: return 0  inc count  while true:    stdout.write &"{count:>2}) Is {x} less than {y} (y/n)? "    let answer = stdin.readLine()[0]    case answer    of 'y': return -1    of 'n': return 1    else: echo "Incorrect answer." var sortedList: seq[string] for elem in list:  sortedList.insert(elem, sortedList.upperBound(elem, comp)) echo "Sorted list: ", sortedList.join(", ")`
Output:
``` 1) Is violet less than red (y/n)? n
2) Is violet less than green (y/n)? n
3) Is red less than green (y/n)? n
4) Is red less than indigo (y/n)? n
5) Is green less than indigo (y/n)? y
6) Is red less than blue (y/n)? n
7) Is indigo less than blue (y/n)? n
8) Is green less than blue (y/n)? n
9) Is indigo less than yellow (y/n)? y
10) Is violet less than yellow (y/n)? y
11) Is red less than orange (y/n)? n
12) Is green less than orange (y/n)? y
13) Is indigo less than orange (y/n)? y
Sorted list: blue, green, indigo, orange, red, violet, yellow```

## OCaml

Standard sort with custom comparator

List:

`let () =  let count = ref 0 in  let mycmp s1 s2 = (    incr count;    Printf.printf "(%d) Is %s <, ==, or > %s? Answer -1, 0, or 1: " (!count) s1 s2;    read_int ()  ) in  let items = ["violet"; "red"; "green"; "indigo"; "blue"; "yellow"; "orange"] in  let sorted = List.sort mycmp items in  List.iter (Printf.printf "%s ") sorted;  print_newline ()`
Output:
```(1) Is violet <, ==, or > red? Answer -1, 0, or 1: 1
(2) Is red <, ==, or > green? Answer -1, 0, or 1: -1
(3) Is violet <, ==, or > green? Answer -1, 0, or 1: 1
(4) Is indigo <, ==, or > blue? Answer -1, 0, or 1: 1
(5) Is yellow <, ==, or > orange? Answer -1, 0, or 1: 1
(6) Is blue <, ==, or > orange? Answer -1, 0, or 1: 1
(7) Is blue <, ==, or > yellow? Answer -1, 0, or 1: 1
(8) Is violet <, ==, or > indigo? Answer -1, 0, or 1: 1
(9) Is green <, ==, or > indigo? Answer -1, 0, or 1: -1
(10) Is green <, ==, or > blue? Answer -1, 0, or 1: -1
(11) Is green <, ==, or > yellow? Answer -1, 0, or 1: 1
(12) Is red <, ==, or > yellow? Answer -1, 0, or 1: -1
(13) Is red <, ==, or > orange? Answer -1, 0, or 1: -1
red orange yellow green blue indigo violet
```

Array:

`let () =  let count = ref 0 in  let mycmp s1 s2 = (    incr count;    Printf.printf "(%d) Is %s <, ==, or > %s? Answer -1, 0, or 1: " (!count) s1 s2;    read_int ()  ) in  let items = [|"violet"; "red"; "green"; "indigo"; "blue"; "yellow"; "orange"|] in  Array.sort mycmp items;  Array.iter (Printf.printf "%s ") items;  print_newline ()`
Output:
```(1) Is blue <, ==, or > yellow? Answer -1, 0, or 1: 1
(2) Is blue <, ==, or > orange? Answer -1, 0, or 1: 1
(3) Is blue <, ==, or > red? Answer -1, 0, or 1: 1
(4) Is blue <, ==, or > green? Answer -1, 0, or 1: 1
(5) Is blue <, ==, or > indigo? Answer -1, 0, or 1: -1
(6) Is indigo <, ==, or > violet? Answer -1, 0, or 1: -1
(7) Is blue <, ==, or > green? Answer -1, 0, or 1: 1
(8) Is blue <, ==, or > indigo? Answer -1, 0, or 1: -1
(9) Is indigo <, ==, or > orange? Answer -1, 0, or 1: 1
(10) Is blue <, ==, or > green? Answer -1, 0, or 1: 1
(11) Is blue <, ==, or > orange? Answer -1, 0, or 1: 1
(12) Is red <, ==, or > yellow? Answer -1, 0, or 1: -1
(13) Is blue <, ==, or > yellow? Answer -1, 0, or 1: 1
(14) Is yellow <, ==, or > green? Answer -1, 0, or 1: -1
(15) Is green <, ==, or > orange? Answer -1, 0, or 1: 1
(16) Is green <, ==, or > red? Answer -1, 0, or 1: 1
(17) Is yellow <, ==, or > red? Answer -1, 0, or 1: 1
(18) Is yellow <, ==, or > orange? Answer -1, 0, or 1: 1
(19) Is orange <, ==, or > red? Answer -1, 0, or 1: 1
red orange yellow green blue indigo violet
```

## Perl

`#!/usr/bin/perl use strict; # https://rosettacode.org/wiki/Order_by_pair_comparisonsuse warnings; sub ask  {  while( 1 )    {    print "Compare \$a to \$b [<,=,>]: ";    <STDIN> =~ /[<=>]/ and return +{qw( < -1 = 0 > 1 )}->{\$&};    }  } my @sorted = sort ask qw( violet red green indigo blue yellow orange );print "sorted: @sorted\n";`
Output:
```Compare violet to red [<,=,>]: >
Compare green to indigo [<,=,>]: <
Compare blue to yellow [<,=,>]: >
Compare red to green [<,=,>]: <
Compare green to violet [<,=,>]: <
Compare violet to indigo [<,=,>]: ?
Compare violet to indigo [<,=,>]: >
Compare yellow to orange [<,=,>]: >
Compare red to orange [<,=,>]: <
Compare orange to green [<,=,>]: <
Compare green to yellow [<,=,>]: >
Compare green to blue [<,=,>]: <
Compare indigo to blue [<,=,>]: >
sorted: red orange yellow green blue indigo violet
```

## Phix

The number of questions asked is entirely dependent on how the initial order marries in with the sorting algorithm.
This needs just 6 questions to handle an already in-order or only first two items swapped list.
I picked an initial ordering that requires a fairly easy to remember set of answers: 4Y then alternate.
The builtin sort(s) use an initial gap of 10%, ultimately balancing #comparisons against cache hits, which leads to a wider range of #questions, as said best case 6, worst case 21. A better match to the narrower range of Python (I think 10..14) could probably be made using a copy of custom_sort (it is only 52 lines) with an initial 50% gap.

```integer qn = 0
qn += 1
printf(1,"%d: Is %s < %s (Y/N)?:",{qn,a,b})
integer ch = upper(wait_key())
printf(1,"%s\n",ch)
return iff(ch='Y'?-1:1)
end function

?custom_sort(ask,split("violet orange red yellow green blue indigo"))
```
Output:
```1: Is orange < violet (Y/N)?:Y
2: Is red < violet (Y/N)?:Y
3: Is red < orange (Y/N)?:Y
4: Is yellow < violet (Y/N)?:Y
5: Is yellow < orange (Y/N)?:N
6: Is green < violet (Y/N)?:Y
7: Is green < yellow (Y/N)?:N
8: Is blue < violet (Y/N)?:Y
9: Is blue < green (Y/N)?:N
10: Is indigo < violet (Y/N)?:Y
11: Is indigo < blue (Y/N)?:N
{"red","orange","yellow","green","blue","indigo","violet"}
```

## Python

### Python: Binary insertion

Uses binary search to insert successive items into a growing ordered list. Comparisons are asked for.

`def _insort_right(a, x, q):    """    Insert item x in list a, and keep it sorted assuming a is sorted.    If x is already in a, insert it to the right of the rightmost x.    """     lo, hi = 0, len(a)    while lo < hi:        mid = (lo+hi)//2        q += 1        less = input(f"{q:2}: IS {x:>6} LESS-THAN {a[mid]:>6} ? y/n: ").strip().lower() == 'y'        if less: hi = mid        else: lo = mid+1    a.insert(lo, x)    return q def order(items):    ordered, q = [], 0    for item in items:        q = _insort_right(ordered, item, q)    return ordered, q if __name__ == '__main__':    items = 'violet red green indigo blue yellow orange'.split()    ans, questions = order(items)    print('\n' + ' '.join(ans))`
Output:
``` 1: IS    red LESS-THAN violet ? y/n: y

2: IS  green LESS-THAN violet ? y/n: y

3: IS  green LESS-THAN    red ? y/n: n

4: IS indigo LESS-THAN  green ? y/n: n

5: IS indigo LESS-THAN violet ? y/n: y

6: IS   blue LESS-THAN indigo ? y/n: y

7: IS   blue LESS-THAN  green ? y/n: n

8: IS yellow LESS-THAN   blue ? y/n: y

9: IS yellow LESS-THAN  green ? y/n: y

10: IS yellow LESS-THAN    red ? y/n: n

11: IS orange LESS-THAN   blue ? y/n: y

12: IS orange LESS-THAN yellow ? y/n: y

13: IS orange LESS-THAN    red ? y/n: n

red orange yellow green blue indigo violet```

### Python: Sort with custom comparator

This uses a custom comparator together with functools.cmp_to_key to sort the previous order in fourteen questions.

`from functools import cmp_to_key def user_cmp(a, b):    return int(input(f"IS {a:>6} <, ==, or > {b:>6}  answer -1, 0 or 1:")) if __name__ == '__main__':    items = 'violet red green indigo blue yellow orange'.split()    ans = sorted(items, key=cmp_to_key(user_cmp))    print('\n' + ' '.join(ans))`
Output:
```IS    red <, ==, or > violet  answer -1, 0 or 1:-1

IS  green <, ==, or >    red  answer -1, 0 or 1:1

IS  green <, ==, or > violet  answer -1, 0 or 1:-1

IS  green <, ==, or >    red  answer -1, 0 or 1:1

IS indigo <, ==, or >  green  answer -1, 0 or 1:1

IS indigo <, ==, or > violet  answer -1, 0 or 1:-1

IS   blue <, ==, or > indigo  answer -1, 0 or 1:-1

IS   blue <, ==, or >  green  answer -1, 0 or 1:1

IS yellow <, ==, or >   blue  answer -1, 0 or 1:-1

IS yellow <, ==, or >  green  answer -1, 0 or 1:-1

IS yellow <, ==, or >    red  answer -1, 0 or 1:1

IS orange <, ==, or >   blue  answer -1, 0 or 1:-1

IS orange <, ==, or > yellow  answer -1, 0 or 1:-1

IS orange <, ==, or >    red  answer -1, 0 or 1:1

red orange yellow green blue indigo violet```

## Quackery

`sortwith` sorts by insertion sort by default, of by merge sort falling back to insertion sort for nests of fewer than 16 items if the Quackery extensions are loaded. In either instance, as this is sorting a nest of seven items, it will be by insertion sort.

` [ \$ "Is " swap join   \$ " before " join   swap join    \$ "? (y/n) " join   input \$ "y" = ]       is askuser \$ "red orange yellow green blue indigo violet"say "Correct order --> "dup echo\$ cr crnest\$ shuffledup witheach [ echo\$ sp ] cr crsortwith askuser crwitheach [ echo\$ sp ] cr`
Output:
```Correct order --> red orange yellow green blue indigo violet

green blue orange indigo yellow violet red

Is blue before green? (y/n) n
Is orange before green? (y/n) y
Is indigo before orange? (y/n) n
Is indigo before green? (y/n) n
Is indigo before blue? (y/n) n
Is yellow before orange? (y/n) n
Is yellow before green? (y/n) y
Is violet before orange? (y/n) n
Is violet before yellow? (y/n) n
Is violet before green? (y/n) n
Is violet before blue? (y/n) n
Is violet before indigo? (y/n) n
Is red before orange? (y/n) y

red orange yellow green blue indigo violet
```

## Raku

Raku's sort (like most languages) can take a custom "comparator" routine. Since the calls to the comparator are minimized, and the info that the user provides is analogous to the required return values of the comparator, we just need to embed the prompt directly in the comparator.

`my \$ask_count = 0;sub by_asking ( \$a, \$b ) {    \$ask_count++;    constant \$fmt = '%2d. Is %-6s [ less than | greater than | equal to ] %-6s? ( < = > ) ';    constant %o = '<' => Order::Less,                  '=' => Order::Same,                  '>' => Order::More;     loop {        my \$input = prompt sprintf \$fmt, \$ask_count, \$a, \$b;        return \$_ with %o{ \$input.trim };        say "Invalid input '\$input'";    }} my @colors = <violet red green indigo blue yellow orange>;my @sorted = @colors.sort: &by_asking;say (:@sorted); die if @sorted».substr(0,1).join ne 'roygbiv';my \$expected_ask_count = @colors.elems * log(@colors.elems);warn "Too many questions? ({:\$ask_count} > {:\$expected_ask_count})" if \$ask_count > \$expected_ask_count;`
Output:
``` 1. Is violet [ less than | greater than | equal to ] red   ? ( < = > ) >
2. Is green  [ less than | greater than | equal to ] indigo? ( < = > ) <
3. Is blue   [ less than | greater than | equal to ] yellow? ( < = > ) >
4. Is red    [ less than | greater than | equal to ] green ? ( < = > ) <
5. Is violet [ less than | greater than | equal to ] green ? ( < = > ) >
6. Is violet [ less than | greater than | equal to ] indigo? ( < = > ) >
7. Is yellow [ less than | greater than | equal to ] orange? ( < = > ) >
8. Is red    [ less than | greater than | equal to ] orange? ( < = > ) <
9. Is green  [ less than | greater than | equal to ] orange? ( < = > ) >
10. Is green  [ less than | greater than | equal to ] yellow? ( < = > ) >
11. Is green  [ less than | greater than | equal to ] blue  ? ( < = > ) <
12. Is indigo [ less than | greater than | equal to ] blue  ? ( < = > ) >
sorted => [red orange yellow green blue indigo violet]
```

## REXX

Translation of: Python

Extra code was added to the REXX program to handle incorrectly formatted answers.

`/*REXX pgm orders some items based on (correct) answers from a  carbon─based life form. */colors= 'violet red green indigo blue yellow orange'                                        q= 0;    #= 0;    \$=           do j=1  for words(colors);   q= inSort( word(colors, j), q)           end   /*j*/                           /*poise questions the CBLF about order.*/say           do i=1  for #;   say '   query'   right(i, length(#) )":"   !.i           end   /*i*/                           /* [↑] show the list of queries to CBLF*/saysay 'final ordering: '    \$exit 0/*──────────────────────────────────────────────────────────────────────────────────────*/getAns: #= # + 1;    _= copies('─', 8);     y_n= '     Answer  y/n'              do try=0  until ansU='Y'  |  ansU='N'              if try>0  then say _ '(***error***)  incorrect answer.'              ask= _  ' is '   center(x,6)   " less than "   center(word(\$, mid+1),6)  '?'              say ask   y_n;  parse pull ans 1 ansU;   ansU= space(ans);   upper ansU              end   /*until*/;      !.#= ask   '  '    ans;                return/*──────────────────────────────────────────────────────────────────────────────────────*/inSort: parse arg x, q;          hi= words(\$);          lo= 0              do q=q-1  while lo<hi;              mid= (lo+hi) % 2              call getAns;  if ansU=='Y'  then hi= mid                                          else lo= mid + 1              end   /*q*/        \$= subword(\$, 1, lo)  x  subword(\$, lo+1);      return q`
output   (only showing the results and eliding the querying/answering):
```   query  1: ────────  is   red    less than  violet ?    y
query  2: ────────  is  green   less than  violet ?    y
query  3: ────────  is  green   less than   red   ?    n
query  4: ────────  is  indigo  less than  green  ?    n
query  5: ────────  is  indigo  less than  violet ?    y
query  6: ────────  is   blue   less than  indigo ?    y
query  7: ────────  is   blue   less than  green  ?    n
query  8: ────────  is  yellow  less than   blue  ?    y
query  9: ────────  is  yellow  less than  green  ?    y
query 10: ────────  is  yellow  less than   red   ?    n
query 11: ────────  is  orange  less than   blue  ?    y
query 12: ────────  is  orange  less than  yellow ?    y
query 13: ────────  is  orange  less than   red   ?    n

final ordering:  red orange yellow green blue indigo violet
```

## Ruby

### Ruby: Binary search insertion sort

`items = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"]count = 0sortedItems = []items.each {|item|  puts "Inserting '#{item}' into #{sortedItems}"  spotToInsert = sortedItems.bsearch_index{|x|    count += 1    print "(#{count}) Is #{item} < #{x}? "    gets.start_with?('y')  } || sortedItems.length # if insertion point is at the end, bsearch_index returns nil  sortedItems.insert(spotToInsert, item)}p sortedItems`
Output:
```Inserting 'violet' into []
Inserting 'red' into ["violet"]
(1) Is red < violet? y
Inserting 'green' into ["red", "violet"]
(2) Is green < violet? y
(3) Is green < red? n
Inserting 'indigo' into ["red", "green", "violet"]
(4) Is indigo < green? n
(5) Is indigo < violet? y
Inserting 'blue' into ["red", "green", "indigo", "violet"]
(6) Is blue < indigo? y
(7) Is blue < green? n
Inserting 'yellow' into ["red", "green", "blue", "indigo", "violet"]
(8) Is yellow < blue? y
(9) Is yellow < green? y
(10) Is yellow < red? n
Inserting 'orange' into ["red", "yellow", "green", "blue", "indigo", "violet"]
(11) Is orange < blue? y
(12) Is orange < yellow? y
(13) Is orange < red? n
["red", "orange", "yellow", "green", "blue", "indigo", "violet"]
```

### Ruby: Standard sort with custom comparator

`items = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"]count = 0p items.sort {|a, b|  count += 1  print "(#{count}) Is #{a} <, =, or > #{b}. Answer -1, 0, or 1: "  gets.to_i}`
Output:
```(1) Is violet <, =, or > red. Answer -1, 0, or 1: 1
(2) Is violet <, =, or > green. Answer -1, 0, or 1: 1
(3) Is red <, =, or > green. Answer -1, 0, or 1: -1
(4) Is violet <, =, or > indigo. Answer -1, 0, or 1: 1
(5) Is green <, =, or > indigo. Answer -1, 0, or 1: -1
(6) Is violet <, =, or > blue. Answer -1, 0, or 1: 1
(7) Is indigo <, =, or > blue. Answer -1, 0, or 1: 1
(8) Is green <, =, or > blue. Answer -1, 0, or 1: -1
(9) Is violet <, =, or > yellow. Answer -1, 0, or 1: 1
(10) Is indigo <, =, or > yellow. Answer -1, 0, or 1: 1
(11) Is blue <, =, or > yellow. Answer -1, 0, or 1: 1
(12) Is green <, =, or > yellow. Answer -1, 0, or 1: 1
(13) Is red <, =, or > yellow. Answer -1, 0, or 1: -1
(14) Is violet <, =, or > orange. Answer -1, 0, or 1: 1
(15) Is indigo <, =, or > orange. Answer -1, 0, or 1: 1
(16) Is blue <, =, or > orange. Answer -1, 0, or 1: 1
(17) Is green <, =, or > orange. Answer -1, 0, or 1: 1
(18) Is yellow <, =, or > orange. Answer -1, 0, or 1: 1
(19) Is red <, =, or > orange. Answer -1, 0, or 1: -1
["red", "orange", "yellow", "green", "blue", "indigo", "violet"]
```

## Wren

Translation of: Python
Library: Wren-ioutil
Library: Wren-fmt
`import "/ioutil" for Inputimport "/fmt" for 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.var insortRight = Fn.new{ |a, x, q|    var lo = 0    var hi = a.count    while (lo < hi) {        var mid = ((lo + hi)/2).floor        q = q + 1        var prompt = Fmt.swrite("\$2d: Is \$6s less than \$6s ? y/n: ", q, x, a[mid])        var less = Input.option(prompt, "yn") == "y"        if (less) {            hi = mid        } else {            lo = mid + 1        }     }     a.insert(lo, x)     return q} var order = Fn.new { |items|    var ordered = []    var q = 0    for (item in items) {        q = insortRight.call(ordered, item, q)    }    return ordered} var items = "violet red green indigo blue yellow orange".split(" ")var ordered = order.call(items)System.print("\nThe colors of the rainbow, in sorted order, are:")System.print(ordered)`
Output:
``` 1: Is    red less than violet ? y/n: y
2: Is  green less than violet ? y/n: y
3: Is  green less than    red ? y/n: n
4: Is indigo less than  green ? y/n: n
5: Is indigo less than violet ? y/n: y
6: Is   blue less than indigo ? y/n: y
7: Is   blue less than  green ? y/n: n
8: Is yellow less than   blue ? y/n: y
9: Is yellow less than  green ? y/n: y
10: Is yellow less than    red ? y/n: n
11: Is orange less than   blue ? y/n: y
12: Is orange less than yellow ? y/n: y
13: Is orange less than    red ? y/n: n

The colors of the rainbow, in sorted order, are:
[red, orange, yellow, green, blue, indigo, violet]
```