Order by pair comparisons: Difference between revisions

* A routine that does not ask the user "too many" comparison questions should be used.

<br><br>

 

=={{header|Arturo}}==

 

count: 0

 

 

print ""

 

{{out}}

 

sorted => [indigo orange yellow green blue red violet]</pre>

 

=={{header|C}}==

Using qsort; not very efficient

#include <string.h>

#include <stdlib.h>

printOrder(items, sizeof(items)/sizeof(*items));

return 0;

{{out}}

<pre>

=={{header|C++}}==

===C++: Binary search insertion sort===

#include <iostream>

#include <vector>

PrintOrder(sortedItems);

return 0;

{{out}}

<pre>

 

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

#include <iostream>

#include <vector>

PrintOrder(items);

return 0;

{{out}}

<pre>

 

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

110 DIM IN$(6), OU$(6)

120 FOR I=0 TO 6:READ IN$(I): NEXT I

410 FOR Q=0 TO N-2:PRINT OU$(Q)",";:NEXT Q

420 PRINT OU$(N-1)")"

{{Out}}

<pre>

=={{header|F_Sharp|F#}}==

This task uses [https://rosettacode.org/wiki/Factorial_base_numbers_indexing_permutations_of_a_collection#F.23 Factorial base numbers indexing permutations of a collection (F#)]

// 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

{{out}}

Possible interaction:

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

{{works with|Factor|0.99 2021-02-05}}

 

qw{ violet red green indigo blue yellow orange }

{{out}}

<pre>

=={{header|FreeBASIC}}==

{{trans|Commodore BASIC}}

Dim Shared As Byte r, n = 1

Dim Shared As String IN1, OU1

PrintOrder

Sleep

 

 

=={{header|Go}}==

===Go: Binary search insertion sort===

import (

}

fmt.Println(sortedItems)

{{out}}

<pre>

 

===Go: Standard sort with custom comparator===

import (

sort.Sort(items)

fmt.Println(items)

{{out}}

<pre>

[red orange yellow green blue indigo violet]

</pre>

 

=={{header|Java}}==

===Java: Binary search insertion sort===

 

public class SortComp1 {

System.out.println(sortedItems);

}

{{out}}

<pre>

 

===Java: Standard sort with custom comparator===

 

public class OrderByPair {

System.out.println(items);

}

{{out}}

<pre>

[red, yellow, green, orange, blue, indigo, violet]

</pre>

 

=={{header|Julia}}==

const ordering = Dict("violet" => 7, "red" => 1, "green" => 4, "indigo" => 6, "blue" => 5,

"yellow" => 3, "orange" => 2)

println("Unsorted: $words")

println("Sorted: $(orderbypair!(words)). Total requests: $(nrequests[1]).")

<pre>

Is violet greater than indigo? (Y/N) => y

Sorted: ["red", "orange", "yellow", "green", "blue", "indigo", "violet"]. Total requests: 14.

</pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

HumanOrderCheck[opt1_,opt2_]:=ChoiceDialog[Row@{"Is {",opt1,", ", opt2, "} ordered?"},{"Yes"->True,"No"->False}]

{{out}}

After some Yes/No clicks you should get:

<pre>{"red", "orange", "yellow", "green", "blue", "indigo", "violet"}</pre>

 

=={{header|Nim}}==

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

 

let list = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"]

sortedList.insert(elem, sortedList.upperBound(elem, comp))

 

 

{{out}}

 

List:

let count = ref 0 in

let mycmp s1 s2 = (

let sorted = List.sort mycmp items in

List.iter (Printf.printf "%s ") sorted;

{{out}}

<pre>

 

Array:

let count = ref 0 in

let mycmp s1 s2 = (

Array.sort mycmp items;

Array.iter (Printf.printf "%s ") items;

{{out}}

<pre>

 

=={{header|Perl}}==

 

use strict; # https://rosettacode.org/wiki/Order_by_pair_comparisons

 

my @sorted = sort ask qw( violet red green indigo blue yellow orange );

{{out}}

<pre>

I picked an initial ordering that requires a fairly easy to remember set of answers: 4Y then alternate.<br>

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.

<span style="color: #004080;">integer</span> <span style="color: #000000;">qn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">ask</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ask</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"violet orange red yellow green blue indigo"</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

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

 

"""

Insert item x in list a, and keep it sorted assuming a is sorted.

items = 'violet red green indigo blue yellow orange'.split()

ans, questions = order(items)

 

{{out}}

This uses a custom comparator together with [https://docs.python.org/3/library/functools.html?highlight=cmp_to_key#functools.cmp_to_key functools.cmp_to_key] to sort the previous order in fourteen questions.

 

 

def user_cmp(a, b):

items = 'violet red green indigo blue yellow orange'.split()

ans = sorted(items, key=cmp_to_key(user_cmp))

 

{{out}}

<code>sortwith</code> 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.

 

$ " before " join

swap join

dup witheach [ echo$ sp ] cr cr

sortwith askuser cr

 

{{out}}

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.

 

sub by_asking ( $a, $b ) {

$ask_count++;

die if @sorted».substr(0,1).join ne 'roygbiv';

my $expected_ask_count = @colors.elems * log(@colors.elems);

{{out}}

<pre>

 

Also note that lists in REXX start with unity, not zero.

colors= 'violet red green indigo blue yellow orange'

q= 0; #= 0; $=

else lo= mid + 1

end /*q*/

{{out|output|text=&nbsp; (only showing the results and eliding the querying/answering):}}

<pre>

=={{header|Ruby}}==

===Ruby: Binary search insertion sort===

count = 0

sortedItems = []

sortedItems.insert(spotToInsert, item)

}

{{out}}

<pre>

 

===Ruby: Standard sort with custom comparator===

count = 0

p items.sort {|a, b|

print "(#{count}) Is #{a} <, =, or > #{b}. Answer -1, 0, or 1: "

gets.to_i

{{out}}

<pre>

{{libheader|Wren-ioutil}}

{{libheader|Wren-fmt}}

 

// Inserts item x in list a, and keeps it sorted assuming a is already sorted.

var ordered = order.call(items)

System.print("\nThe colors of the rainbow, in sorted order, are:")

 

{{out}}

The colors of the rainbow, in sorted order, are:

[red, orange, yellow, green, blue, indigo, violet]

</pre>