Order by pair comparisons: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|C++}}: add c++ way using standard sort)
Line 30: Line 30:


=={{header|C++}}==
=={{header|C++}}==
===C++: Binary search insertion sort===
<lang cpp>#include <algorithm>
<lang cpp>#include <algorithm>
#include <iostream>
#include <iostream>
Line 74: Line 75:
sortedItems.insert(spotToInsert, item);
sortedItems.insert(spotToInsert, item);
}
}
PrintOrder(sortedItems);
PrintOrder(sortedItems);
return 0;
⚫
}
</lang>
}</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 102: Line 103:
</pre>
</pre>


===C++: STL sort with custom comparator===
<lang cpp>#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;
}</lang>
{{out}}
<pre>
(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 }
</pre>


=={{header|Commodore BASIC}}==
=={{header|Commodore BASIC}}==

Revision as of 06:39, 1 June 2021

Task
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

Heap sort | Merge sort | Patience sort | Quick sort

O(n log2n) sorts
Shell Sort

O(n2) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree 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:

  • Asking for/receiving user comparisons is a part of the task.
  • 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.



C++

C++: Binary search insertion sort

<lang cpp>#include <algorithm>

  1. include <iostream>
  2. 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 reqired
   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;

}</lang>

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

<lang cpp>#include <algorithm>

  1. include <iostream>
  2. 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;

}</lang>

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

<lang basic>100 REM SORT BY COMPARISON 110 DIM IN$(6), OU$(6) 120 FOR I=0 TO 6:READ IN$(I): NEXT I 130 DATA VIOLET,RED,GREEN,INDIGO,BLUE,YELLOW,ORANGE 140 OU$(0)=IN$(0):N=1 150 FOR I=1 TO 6 160 : IN$=IN$(I) 180 : GOSUB 390 190 : FOR J=0 TO N-1 200 : OU$ = OU$(J) 210 : GOSUB 340 220 : IF R>=0 THEN 280 230 : FOR K=N TO J+1 STEP -1 240 : OU$(K) = OU$(K-1) 250 : NEXT K 260 : OU$(J) = IN$ 270 : GOTO 300 280 : NEXT J 290 : OU$(N) = IN$ 300 : N=N+1 310 NEXT I 320 GOSUB 390 330 END 340 PRINT "IS "IN$" < "OU$"? (Y/N)"; 350 GET K$: IF K$<>"Y" AND K$<>"N" THEN 350 360 PRINT K$ 370 R = K$="Y" 380 RETURN 390 PRINT "("; 400 IF N=1 THEN 420 410 FOR Q=0 TO N-2:PRINT OU$(Q)",";:NEXT Q 420 PRINT OU$(N-1)")" 430 RETURN</lang>

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#

This example is incorrect. Please fix the code and remove this message.

Details: Does not prompt user

<lang fsharp> // Order by pair comparisons. Nigel Galloway: April 23rd., 2021 type colours= Violet |Red |Green |Indigo |Blue |Yellow |Orange let fN,fG=let mutable z=0 in ((fun()->z),(fun n g->z<-z+1; compare n g)) printfn "[Red;Orange;Yellow;Green;Blue;Indigo;Violet] sorted to %A using %d comparisons" ([Red;Orange;Yellow;Green;Blue;Indigo;Violet]|>List.sortWith(fun n g->fG n g)) (fN()) </lang>

Output:
[Red;Orange;Yellow;Green;Blue;Indigo;Violet] sorted to [Violet; Red; Green; Indigo; Blue; Yellow; Orange] using 25 comparisons

Factor

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

Works with: Factor version 0.99 2021-02-05

<lang factor>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 .</lang>

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" }

Julia

<lang 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
   end

end

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 a

end

const words = String.(split("violet red green indigo blue yellow orange", r"\s+")) println("Unsorted: $words") println("Sorted: $(orderbypair!(words)). Total requests: $(nrequests[1]).")

</lang>

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.

Nim

Using a list filled by binary insertion and a custom comparison function. <lang Nim>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(", ")</lang>

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

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Order_by_pair_comparisons use 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";</lang>

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
function ask(string a, b)
    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.

<lang python>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))</lang>
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.

<lang python>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))</lang>
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

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.

<lang perl6>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;</lang>

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.

Also note that lists in REXX start with unity, not zero. <lang>/*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*/

say say '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</lang>
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

Wren

Translation of: Python
Library: Wren-ioutil
Library: Wren-fmt

<lang ecmascript>import "/ioutil" for Input import "/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)</lang>

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]
Retrieved from "https://rosettacode.org/wiki/Order_by_pair_comparisons?oldid=311527"