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|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#}}==

// Order by pair comparisons. Nigel Galloway: April 23rd., 2021

{{out}}

<pre>

</pre>

 

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>

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

</pre>

 

=={{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

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

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

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

13) Is indigo less than orange (y/n)? y

Sorted list: blue, green, indigo, orange, red, violet, yellow</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}}

 

red orange yellow green blue indigo violet</pre>

 

=={{header|Raku}}==

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 = []

print "(#{count}) Is #{item} < #{x}? "

gets.start_with?('y')

sortedItems.insert(spotToInsert, item)

}

{{out}}

<pre>

(12) Is orange < yellow? y

(13) Is orange < red? n

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