Order by pair comparisons: Difference between revisions

{{trans|Python: Sort with custom comparator}}

 

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

 

{{out}}

 

=={{header|Action!}}==

 

PROC PrintArray(PTR ARRAY a BYTE size)

PutE() Print("Sorted array: ")

PrintArray(arr,COUNT)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Order_by_pair_comparisons.png Screenshot from Atari 8-bit computer]

=={{header|Arturo}}==

 

count: 0

 

 

print ""

 

{{out}}

 

=={{header|AutoHotkey}}==

result := [], num := 0, Questions :=""

 

output .= color ", "

MsgBox % Questions "`nSorted Output :`n" Trim(output, ", ")

 

{{out}}

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

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 [[https://hackage.haskell.org/package/monadlist]] contains monadic variants of most popular list operations so that it becomes easy to implement our favorite sorting algorithms.

 

import Control.Monad.ListM (sortByM, insertByM, partitionM, minimumByM)

import Data.Bool (bool)

go (h:t) = do (l, g) <- partitionM (fmap (LT /=) . cmp h) t

go l <+> pure [h] <+> go g

 

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

We are ready to ask user to compare entries for us:

putStr $ show a ++ " ≤ " ++ show b ++ " ? [y/n] "

bool GT LT . ("y" ==) <$> getLine

 

 

<pre>*Main> isortM ask colors

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.

 

mapM_ showHist $ hist res

putStrLn $ "Median number of comparisons: " ++ show (median res)

line = show n ++ "\t" ++ bar ++ " " ++ show perc ++ "%"

bar = replicate (max perc 1) '*'

 

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

 

=={{header|J}}==

sel=: {{ u#[ }}

 

LT=: <:%=i.#items

askless quicksort y

 

Is indigo less than violet? yes

Is indigo less than red? no

Is green less than blue? yes

Is red less than orange? yes

 

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

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 r:

$prompt | stderr

| order as $ordered

| ("\nThe colors of the rainbow, in sorted order, are:",

 

'''Recommended Invocation Options''': -nRrc

 

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

 

=={{header|Lua}}==

print("unsorted: " .. table.concat(colors," "))

known, notyn, nc, nq = {}, {n="y",y="n"}, 0, 0

end)

print("sorted: " .. table.concat(colors," "))

{{out}}

<pre>unsorted: violet red green indigo blue yellow orange

 

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