Order by pair comparisons: Difference between revisions
m (→{{header|Wren}}: Minor tidy) |
|||
(29 intermediate revisions by 17 users not shown) | |||
Line 28: | Line 28: | ||
* A routine that does not ask the user "too many" comparison questions should be used. |
* A routine that does not ask the user "too many" comparison questions should be used. |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python: Sort with custom comparator}} |
|||
<syntaxhighlight lang="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(‘ ’))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="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 |
|||
OD |
|||
RETURN |
|||
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</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Order_by_pair_comparisons.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">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]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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]</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|C}}== |
|||
Using qsort; not very efficient |
|||
<syntaxhighlight lang="c">#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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(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 } |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
===C++: Binary search insertion sort=== |
|||
<lang cpp>#include <algorithm> |
|||
<syntaxhighlight lang="cpp">#include <algorithm> |
|||
#include <iostream> |
#include <iostream> |
||
#include <vector> |
#include <vector> |
||
Line 63: | Line 348: | ||
// Use a binary insertion sort to order the items. It should ask for |
// Use a binary insertion sort to order the items. It should ask for |
||
// close to the minimum number of questions |
// close to the minimum number of questions required |
||
for(auto& item : items) |
for(auto& item : items) |
||
{ |
{ |
||
Line 74: | Line 359: | ||
sortedItems.insert(spotToInsert, item); |
sortedItems.insert(spotToInsert, item); |
||
} |
} |
||
PrintOrder(sortedItems); |
PrintOrder(sortedItems); |
||
return 0; |
|||
} |
|||
}</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 102: | Line 387: | ||
</pre> |
</pre> |
||
===C++: STL sort with custom comparator=== |
|||
<syntaxhighlight 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; |
|||
}</syntaxhighlight> |
|||
{{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}}== |
||
< |
<syntaxhighlight lang="basic">100 REM SORT BY COMPARISON |
||
110 DIM IN$(6), OU$(6) |
110 DIM IN$(6), OU$(6) |
||
120 FOR I=0 TO 6:READ IN$(I): NEXT I |
120 FOR I=0 TO 6:READ IN$(I): NEXT I |
||
Line 136: | Line 474: | ||
410 FOR Q=0 TO N-2:PRINT OU$(Q)",";:NEXT Q |
410 FOR Q=0 TO N-2:PRINT OU$(Q)",";:NEXT Q |
||
420 PRINT OU$(N-1)")" |
420 PRINT OU$(N-1)")" |
||
430 RETURN</ |
430 RETURN</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 155: | Line 493: | ||
=={{header|F_Sharp|F#}}== |
=={{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#)] |
|||
{{incorrect|F_Sharp|Does not prompt user}} |
|||
< |
<syntaxhighlight lang="fsharp"> |
||
// Order by pair comparisons. Nigel Galloway: April 23rd., 2021 |
// 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"|] |
|||
type colours= Violet |Red |Green |Indigo |Blue |Yellow |Orange |
|||
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 fN,fG=let mutable z=0 in ((fun()->z),(fun n g->z<-z+1; compare n g)) |
|||
printfn " |
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 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Possible interaction: |
|||
<pre> |
<pre> |
||
Is Indigo less than Orange |
|||
[Red;Orange;Yellow;Green;Blue;Indigo;Violet] sorted to [Violet; Red; Green; Indigo; Blue; Yellow; Orange] using 25 comparisons |
|||
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 |
|||
</pre> |
</pre> |
||
Line 170: | Line 549: | ||
Asking the user for an ordering specifier inside a custom comparator: |
Asking the user for an ordering specifier inside a custom comparator: |
||
{{works with|Factor|0.99 2021-02-05}} |
{{works with|Factor|0.99 2021-02-05}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting io kernel math.order prettyprint qw sorting ; |
||
qw{ violet red green indigo blue yellow orange } |
qw{ violet red green indigo blue yellow orange } |
||
[ "Is %s > %s? (y/n) " printf readln "y" = +gt+ +lt+ ? ] sort .</ |
[ "Is %s > %s? (y/n) " printf readln "y" = +gt+ +lt+ ? ] sort .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 190: | Line 569: | ||
{ "red" "orange" "yellow" "green" "blue" "indigo" "violet" } |
{ "red" "orange" "yellow" "green" "blue" "indigo" "violet" } |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
{{trans|Commodore BASIC}} |
|||
<syntaxhighlight lang="freebasic"> |
|||
Dim Shared As Byte r, n = 1 |
|||
Dim Shared As String IN1, OU1 |
|||
Dim Shared As String IN(6), OU(6) |
|||
Dim As Byte i, j, k |
|||
For i = 0 To 6 : Read IN(i) : Next i |
|||
Data "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 += 1 |
|||
Next i |
|||
PrintOrder |
|||
Sleep |
|||
</syntaxhighlight> |
|||
=={{header|Go}}== |
|||
===Go: Binary search insertion sort=== |
|||
<syntaxhighlight lang="go">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) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
===Go: Standard sort with custom comparator=== |
|||
<syntaxhighlight lang="go">package main |
|||
import ( |
|||
"fmt" |
|||
"sort" |
|||
"strings" |
|||
) |
|||
var count int = 0 |
|||
type sortable []string |
|||
func (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) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(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] |
|||
</pre> |
|||
=={{header|Haskell}}== |
|||
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. |
|||
<syntaxhighlight lang="haskell">import Control.Monad |
|||
import Control.Monad.ListM (sortByM, insertByM, partitionM, minimumByM) |
|||
import Data.Bool (bool) |
|||
import Data.Monoid |
|||
import Data.List |
|||
-------------------------------------------------------------------------------- |
|||
isortM, msortM, tsortM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a] |
|||
-- merge sort from the Control.Monad.ListM library |
|||
msortM = sortByM |
|||
-- insertion sort |
|||
isortM 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 (++)</syntaxhighlight> |
|||
Now we can sort lists with effects. For example, we may count number of comparisons, using writer monad: |
|||
<pre>*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])</pre> |
|||
Or use a "database" as a reference for sorting, using reader monad |
|||
<pre>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]</pre> |
|||
Or even generate all possible permutations of a list making comparisons ambiguous: |
|||
<pre>*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]]</pre> |
|||
We are ready to ask user to compare entries for us: |
|||
<syntaxhighlight lang="haskell">ask a b = do |
|||
putStr $ show a ++ " ≤ " ++ show b ++ " ? [y/n] " |
|||
bool GT LT . ("y" ==) <$> getLine |
|||
colors = ["Violet", "Red", "Green", "Indigo", "Blue", "Yellow", "Orange"]</syntaxhighlight> |
|||
<pre>*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"] |
|||
*Main> msortM ask colors |
|||
"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"] |
|||
*Main> tsortM ask colors |
|||
"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"]</pre> |
|||
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. |
|||
<syntaxhighlight lang="haskell">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]</syntaxhighlight> |
|||
Comparing these three methods gives that for random inputs tree sort is the best choice. |
|||
<pre>*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</pre> |
|||
=={{header|J}}== |
|||
Implementation (here we assume that ordering is transitive):<syntaxhighlight lang="j">require'general/misc/prompt' |
|||
sel=: {{ u#[ }} |
|||
quicksort=: {{ |
|||
if. 1 >: #y do. y |
|||
else. |
|||
(u quicksort y u sel e),(y =sel e),u quicksort y u~ sel e=.y{~?#y |
|||
end. |
|||
}} |
|||
ptc=: {{ |
|||
t=. (+. +./ .*.~)^:_ y=1 |
|||
j=. I.,t+.|:t |
|||
($y)$(j{,t) j} ,y |
|||
}} |
|||
askless=: {{ |
|||
coord=. x ,&(items&i.) y |
|||
lt=. LT {~<coord |
|||
if. 1<lt do. |
|||
lt=. 'y' e. tolower prompt 'Is ',(":;x),' less than ',(":;y),'? ' |
|||
LT=: ptc (lt,-.lt) (coord;|.coord)} LT |
|||
end. |
|||
lt |
|||
}}"0 |
|||
asksort=: {{ |
|||
items=: ~.y |
|||
LT=: <:%=i.#items |
|||
askless quicksort y |
|||
}}</syntaxhighlight> |
|||
Task example:<syntaxhighlight lang="j"> asksort&.;:' violet red green indigo blue yellow orange' |
|||
Is indigo less than violet? yes |
|||
Is indigo less than red? no |
|||
Is indigo less than green? no |
|||
Is indigo less than blue? no |
|||
Is indigo less than yellow? no |
|||
Is indigo less than orange? no |
|||
Is yellow less than red? no |
|||
Is yellow less than green? yes |
|||
Is yellow less than blue? yes |
|||
Is yellow less than orange? no |
|||
Is green less than blue? yes |
|||
Is red less than orange? yes |
|||
red orange yellow green blue indigo violet</syntaxhighlight> |
|||
=={{header|Java}}== |
|||
===Java: Binary search insertion sort=== |
|||
<syntaxhighlight lang="java">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); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
===Java: Standard sort with custom comparator=== |
|||
<syntaxhighlight lang="java">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); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(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] |
|||
</pre> |
|||
=={{header|jq}}== |
|||
{{trans|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. |
|||
<syntaxhighlight lang="jq">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 )</syntaxhighlight> |
|||
'''Recommended Invocation Options''': -nRrc |
|||
'''Sample Transcript''' |
|||
<pre> |
|||
"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"] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">const nrequests = [0] |
||
const ordering = Dict("violet" => 7, "red" => 1, "green" => 4, "indigo" => 6, "blue" => 5, |
const ordering = Dict("violet" => 7, "red" => 1, "green" => 4, "indigo" => 6, "blue" => 5, |
||
"yellow" => 3, "orange" => 2) |
"yellow" => 3, "orange" => 2) |
||
Line 232: | Line 1,164: | ||
println("Unsorted: $words") |
println("Unsorted: $words") |
||
println("Sorted: $(orderbypair!(words)). Total requests: $(nrequests[1]).") |
println("Sorted: $(orderbypair!(words)). Total requests: $(nrequests[1]).") |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Is violet greater than indigo? (Y/N) => y |
Is violet greater than indigo? (Y/N) => y |
||
Line 249: | Line 1,181: | ||
Is indigo greater than violet? (Y/N) => n |
Is indigo greater than violet? (Y/N) => n |
||
Sorted: ["red", "orange", "yellow", "green", "blue", "indigo", "violet"]. Total requests: 14. |
Sorted: ["red", "orange", "yellow", "green", "blue", "indigo", "violet"]. Total requests: 14. |
||
</pre> |
|||
=={{header|Lua}}== |
|||
<syntaxhighlight lang="lua">colors = { "violet", "red", "green", "indigo", "blue", "yellow", "orange" } |
|||
print("unsorted: " .. table.concat(colors," ")) |
|||
known, notyn, nc, nq = {}, {n="y",y="n"}, 0, 0 |
|||
table.sort(colors, function(a,b) |
|||
nc = nc + 1 |
|||
if not known[a] then known[a]={[a]="n"} end |
|||
if not known[b] then known[b]={[b]="n"} end |
|||
if not (known[a][b] or known[b][a]) then |
|||
io.write("Is '" .. a .. "' < '" .. b .."'? (y/n): ") |
|||
nq, known[a][b] = nq+1, io.read() |
|||
if a~=b then known[b][a] = notyn[known[a][b]] end |
|||
end |
|||
return known[a][b]=="y" |
|||
end) |
|||
print("sorted: " .. table.concat(colors," ")) |
|||
print("(" .. nq .. " questions needed to resolve " .. nc .. " comparisons)")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>unsorted: violet red green indigo blue yellow orange |
|||
Is 'orange' < 'violet'? (y/n): y |
|||
Is 'indigo' < 'orange'? (y/n): n |
|||
Is 'violet' < 'indigo'? (y/n): n |
|||
Is 'red' < 'indigo'? (y/n): y |
|||
Is 'green' < 'indigo'? (y/n): y |
|||
Is 'yellow' < 'indigo'? (y/n): y |
|||
Is 'blue' < 'indigo'? (y/n): y |
|||
Is 'blue' < 'orange'? (y/n): n |
|||
Is 'green' < 'orange'? (y/n): n |
|||
Is 'blue' < 'green'? (y/n): n |
|||
Is 'red' < 'green'? (y/n): y |
|||
Is 'yellow' < 'green'? (y/n): y |
|||
Is 'yellow' < 'orange'? (y/n): n |
|||
Is 'red' < 'orange'? (y/n): y |
|||
sorted: red orange yellow green blue indigo violet |
|||
(14 questions needed to resolve 18 comparisons)</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">ClearAll[HumanOrderCheck] |
|||
HumanOrderCheck[opt1_,opt2_]:=ChoiceDialog[Row@{"Is {",opt1,", ", opt2, "} ordered?"},{"Yes"->True,"No"->False}] |
|||
Sort[{"violet","red","green","indigo","blue","yellow","orange"},HumanOrderCheck]</syntaxhighlight> |
|||
{{out}} |
|||
After some Yes/No clicks you should get: |
|||
<pre>{"red", "orange", "yellow", "green", "blue", "indigo", "violet"}</pre> |
|||
=={{header|MiniScript}}== |
|||
<syntaxhighlight lang="miniscript"> |
|||
insertSort = function(arr, item) |
|||
lo = 0 |
|||
hi = arr.len |
|||
while lo < hi |
|||
mid = floor((lo + hi) / 2) |
|||
ans = input("Is " + item + " less than " + arr[mid] + "? y/n: ") |
|||
ans = ans[0].lower |
|||
if ans == "y" then |
|||
hi = mid |
|||
else |
|||
lo = mid + 1 |
|||
end if |
|||
end while |
|||
arr.insert(lo, item) |
|||
end function |
|||
items = "violet red green indigo blue yellow orange".split |
|||
ordered = [] |
|||
for item in items |
|||
insertSort(ordered, item) |
|||
end for |
|||
print ordered |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Is red less than violet? y/n: y |
|||
Is green less than violet? y/n: y |
|||
Is green less than red? y/n: n |
|||
Is indigo less than green? y/n: n |
|||
Is indigo less than violet? y/n: y |
|||
Is blue less than indigo? y/n: y |
|||
Is blue less than green? y/n: n |
|||
Is yellow less than blue? y/n: y |
|||
Is yellow less than green? y/n: y |
|||
Is yellow less than red? y/n: n |
|||
Is orange less than blue? y/n: y |
|||
Is orange less than yellow? y/n: y |
|||
Is orange less than red? y/n: n |
|||
["red", "orange", "yellow", "green", "blue", "indigo", "violet"] |
|||
</pre> |
</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Using a list filled by binary insertion and a custom comparison function. |
Using a list filled by binary insertion and a custom comparison function. |
||
< |
<syntaxhighlight lang="nim">import algorithm, strformat, strutils |
||
let list = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"] |
let list = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"] |
||
Line 275: | Line 1,294: | ||
sortedList.insert(elem, sortedList.upperBound(elem, comp)) |
sortedList.insert(elem, sortedList.upperBound(elem, comp)) |
||
echo "Sorted list: ", sortedList.join(", ")</ |
echo "Sorted list: ", sortedList.join(", ")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 292: | Line 1,311: | ||
13) Is indigo less than orange (y/n)? y |
13) Is indigo less than orange (y/n)? y |
||
Sorted list: blue, green, indigo, orange, red, violet, yellow</pre> |
Sorted list: blue, green, indigo, orange, red, violet, yellow</pre> |
||
=={{header|OCaml}}== |
|||
Standard sort with custom comparator |
|||
List: |
|||
<syntaxhighlight lang="ocaml">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 ()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(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 |
|||
</pre> |
|||
Array: |
|||
<syntaxhighlight lang="ocaml">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 ()</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(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 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Order_by_pair_comparisons |
use strict; # https://rosettacode.org/wiki/Order_by_pair_comparisons |
||
Line 309: | Line 1,397: | ||
my @sorted = sort ask qw( violet red green indigo blue yellow orange ); |
my @sorted = sort ask qw( violet red green indigo blue yellow orange ); |
||
print "sorted: @sorted\n";</ |
print "sorted: @sorted\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 334: | Line 1,422: | ||
I picked an initial ordering that requires a fairly easy to remember set of answers: 4Y then alternate.<br> |
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. |
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. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(notonline)--> |
||
<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: #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: #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> |
||
Line 345: | Line 1,433: | ||
<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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 366: | Line 1,454: | ||
Uses binary search to insert successive items into a growing ordered list. Comparisons are asked for. |
Uses binary search to insert successive items into a growing ordered list. Comparisons are asked for. |
||
< |
<syntaxhighlight lang="python">def _insort_right(a, x, q): |
||
""" |
""" |
||
Insert item x in list a, and keep it sorted assuming a is sorted. |
Insert item x in list a, and keep it sorted assuming a is sorted. |
||
Line 391: | Line 1,479: | ||
items = 'violet red green indigo blue yellow orange'.split() |
items = 'violet red green indigo blue yellow orange'.split() |
||
ans, questions = order(items) |
ans, questions = order(items) |
||
print('\n' + ' '.join(ans))</ |
print('\n' + ' '.join(ans))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 425: | Line 1,513: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="python">from functools import cmp_to_key |
||
def user_cmp(a, b): |
def user_cmp(a, b): |
||
Line 433: | Line 1,521: | ||
items = 'violet red green indigo blue yellow orange'.split() |
items = 'violet red green indigo blue yellow orange'.split() |
||
ans = sorted(items, key=cmp_to_key(user_cmp)) |
ans = sorted(items, key=cmp_to_key(user_cmp)) |
||
print('\n' + ' '.join(ans))</ |
print('\n' + ' '.join(ans))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 465: | Line 1,553: | ||
red orange yellow green blue indigo violet</pre> |
red orange yellow green blue indigo violet</pre> |
||
=={{header|Quackery}}== |
|||
<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. |
|||
<syntaxhighlight lang="quackery"> [ $ "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 cr |
|||
nest$ shuffle |
|||
dup witheach [ echo$ sp ] cr cr |
|||
sortwith askuser cr |
|||
witheach [ echo$ sp ] cr</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 470: | Line 1,599: | ||
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. |
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 |
<syntaxhighlight lang="raku" line>my $ask_count = 0; |
||
sub by_asking ( $a, $b ) { |
sub by_asking ( $a, $b ) { |
||
$ask_count++; |
$ask_count++; |
||
Line 491: | Line 1,620: | ||
die if @sorted».substr(0,1).join ne 'roygbiv'; |
die if @sorted».substr(0,1).join ne 'roygbiv'; |
||
my $expected_ask_count = @colors.elems * log(@colors.elems); |
my $expected_ask_count = @colors.elems * log(@colors.elems); |
||
warn "Too many questions? ({:$ask_count} > {:$expected_ask_count})" if $ask_count > $expected_ask_count;</ |
warn "Too many questions? ({:$ask_count} > {:$expected_ask_count})" if $ask_count > $expected_ask_count;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 516: | Line 1,645: | ||
Also note that lists in REXX start with unity, not zero. |
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. */ |
<syntaxhighlight lang="rexx">/*REXX pgm orders some items based on (correct) answers from a carbon─based life form. */ |
||
colors= 'violet red green indigo blue yellow orange' |
colors= 'violet red green indigo blue yellow orange' |
||
q= 0; #= 0; $= |
q= 0; #= 0; $= |
||
Line 540: | Line 1,669: | ||
else lo= mid + 1 |
else lo= mid + 1 |
||
end /*q*/ |
end /*q*/ |
||
$= subword($, 1, lo) x subword($, lo+1); return q</ |
$= subword($, 1, lo) x subword($, lo+1); return q</syntaxhighlight> |
||
{{out|output|text= (only showing the results and eliding the querying/answering):}} |
{{out|output|text= (only showing the results and eliding the querying/answering):}} |
||
<pre> |
<pre> |
||
Line 558: | Line 1,687: | ||
final ordering: red orange yellow green blue indigo violet |
final ordering: red orange yellow green blue indigo violet |
||
</pre> |
|||
=={{header|Ruby}}== |
|||
===Ruby: Binary search insertion sort=== |
|||
<syntaxhighlight lang="ruby">items = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"] |
|||
count = 0 |
|||
sortedItems = [] |
|||
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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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"] |
|||
</pre> |
|||
===Ruby: Standard sort with custom comparator=== |
|||
<syntaxhighlight lang="ruby">items = ["violet", "red", "green", "indigo", "blue", "yellow", "orange"] |
|||
count = 0 |
|||
p items.sort {|a, b| |
|||
count += 1 |
|||
print "(#{count}) Is #{a} <, =, or > #{b}. Answer -1, 0, or 1: " |
|||
gets.to_i |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(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"] |
|||
</pre> |
</pre> |
||
Line 564: | Line 1,765: | ||
{{libheader|Wren-ioutil}} |
{{libheader|Wren-ioutil}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./ioutil" for Input |
||
import "/fmt" for Fmt |
import "./fmt" for Fmt |
||
// Inserts item x in list a, and keeps it sorted assuming a is already sorted. |
// Inserts item x in list a, and keeps it sorted assuming a is already sorted. |
||
Line 599: | Line 1,800: | ||
var ordered = order.call(items) |
var ordered = order.call(items) |
||
System.print("\nThe colors of the rainbow, in sorted order, are:") |
System.print("\nThe colors of the rainbow, in sorted order, are:") |
||
System.print(ordered)</ |
System.print(ordered)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 619: | Line 1,820: | ||
The colors of the rainbow, in sorted order, are: |
The colors of the rainbow, in sorted order, are: |
||
[red, orange, yellow, green, blue, indigo, violet] |
[red, orange, yellow, green, blue, indigo, violet] |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang "XPL0">include xpllib; \for Print |
|||
int Items, Size, I, J, Gap, JG, T, C, Count; |
|||
[Items:= ["violet", "red", "green", "indigo", "blue", "yellow", "orange"]; |
|||
Size:= 7; |
|||
Count:= 0; |
|||
Gap:= Size>>1; |
|||
while Gap > 0 do |
|||
[for I:= Gap to Size-1 do |
|||
[J:= I - Gap; |
|||
loop [JG:= J + Gap; |
|||
Count:= Count+1; |
|||
Print("%2d: Is %6s less than %6s (y/n)? ", |
|||
Count, Items(J), Items(JG)); |
|||
repeat OpenI(1); |
|||
C:= ChIn(1); |
|||
until C=^y or C=^n; |
|||
ChOut(0, C); CrLf(0); |
|||
if C = ^y then quit; |
|||
T:= Items(J); Items(J):= Items(JG); Items(JG):= T; |
|||
J:= J - Gap; |
|||
if J < 0 then quit; |
|||
]; |
|||
]; |
|||
Gap:= Gap>>1; |
|||
]; |
|||
Print("The colors of the rainbow, in sorted order, are:\n"); |
|||
for I:= 0 to Size-2 do Print("%s, ", Items(I)); |
|||
Print("%s\n", Items(I)); |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1: Is violet less than indigo (y/n)? n |
|||
2: Is red less than blue (y/n)? y |
|||
3: Is green less than yellow (y/n)? n |
|||
4: Is violet less than orange (y/n)? n |
|||
5: Is indigo less than orange (y/n)? n |
|||
6: Is orange less than red (y/n)? n |
|||
7: Is orange less than yellow (y/n)? y |
|||
8: Is yellow less than indigo (y/n)? y |
|||
9: Is indigo less than blue (y/n)? n |
|||
10: Is yellow less than blue (y/n)? y |
|||
11: Is indigo less than green (y/n)? n |
|||
12: Is blue less than green (y/n)? n |
|||
13: Is yellow less than green (y/n)? y |
|||
14: Is indigo less than violet (y/n)? y |
|||
The colors of the rainbow, in sorted order, are: |
|||
red, orange, yellow, green, blue, indigo, violet |
|||
</pre> |
</pre> |
Latest revision as of 09:53, 9 January 2024
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:
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.
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
OD
RETURN
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:
Screenshot from Atari 8-bit computer
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 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
- 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 task uses 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
- 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:
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
Dim Shared As Byte r, n = 1
Dim Shared As String IN1, OU1
Dim Shared As String IN(6), OU(6)
Dim As Byte i, j, k
For i = 0 To 6 : Read IN(i) : Next i
Data "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 += 1
Next i
PrintOrder
Sleep
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 []string
func (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]
Haskell
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.Monad
import Control.Monad.ListM (sortByM, insertByM, partitionM, minimumByM)
import Data.Bool (bool)
import Data.Monoid
import Data.List
--------------------------------------------------------------------------------
isortM, msortM, tsortM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a]
-- merge sort from the Control.Monad.ListM library
msortM = sortByM
-- insertion sort
isortM 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]]
We are ready to ask user to compare entries for us:
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"] *Main> msortM ask colors "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"] *Main> tsortM ask colors "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
J
Implementation (here we assume that ordering is transitive):
require'general/misc/prompt'
sel=: {{ u#[ }}
quicksort=: {{
if. 1 >: #y do. y
else.
(u quicksort y u sel e),(y =sel e),u quicksort y u~ sel e=.y{~?#y
end.
}}
ptc=: {{
t=. (+. +./ .*.~)^:_ y=1
j=. I.,t+.|:t
($y)$(j{,t) j} ,y
}}
askless=: {{
coord=. x ,&(items&i.) y
lt=. LT {~<coord
if. 1<lt do.
lt=. 'y' e. tolower prompt 'Is ',(":;x),' less than ',(":;y),'? '
LT=: ptc (lt,-.lt) (coord;|.coord)} LT
end.
lt
}}"0
asksort=: {{
items=: ~.y
LT=: <:%=i.#items
askless quicksort y
}}
Task example:
asksort&.;:' violet red green indigo blue yellow orange'
Is indigo less than violet? yes
Is indigo less than red? no
Is indigo less than green? no
Is indigo less than blue? no
Is indigo less than yellow? no
Is indigo less than orange? no
Is yellow less than red? no
Is yellow less than green? yes
Is yellow less than blue? yes
Is yellow less than orange? no
Is green less than blue? yes
Is red less than orange? yes
red orange yellow green blue indigo violet
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
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
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]).")
- 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.
Lua
colors = { "violet", "red", "green", "indigo", "blue", "yellow", "orange" }
print("unsorted: " .. table.concat(colors," "))
known, notyn, nc, nq = {}, {n="y",y="n"}, 0, 0
table.sort(colors, function(a,b)
nc = nc + 1
if not known[a] then known[a]={[a]="n"} end
if not known[b] then known[b]={[b]="n"} end
if not (known[a][b] or known[b][a]) then
io.write("Is '" .. a .. "' < '" .. b .."'? (y/n): ")
nq, known[a][b] = nq+1, io.read()
if a~=b then known[b][a] = notyn[known[a][b]] end
end
return known[a][b]=="y"
end)
print("sorted: " .. table.concat(colors," "))
print("(" .. nq .. " questions needed to resolve " .. nc .. " comparisons)")
- Output:
unsorted: violet red green indigo blue yellow orange Is 'orange' < 'violet'? (y/n): y Is 'indigo' < 'orange'? (y/n): n Is 'violet' < 'indigo'? (y/n): n Is 'red' < 'indigo'? (y/n): y Is 'green' < 'indigo'? (y/n): y Is 'yellow' < 'indigo'? (y/n): y Is 'blue' < 'indigo'? (y/n): y Is 'blue' < 'orange'? (y/n): n Is 'green' < 'orange'? (y/n): n Is 'blue' < 'green'? (y/n): n Is 'red' < 'green'? (y/n): y Is 'yellow' < 'green'? (y/n): y Is 'yellow' < 'orange'? (y/n): n Is 'red' < 'orange'? (y/n): y sorted: red orange yellow green blue indigo violet (14 questions needed to resolve 18 comparisons)
Mathematica / Wolfram Language
ClearAll[HumanOrderCheck]
HumanOrderCheck[opt1_,opt2_]:=ChoiceDialog[Row@{"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"}
MiniScript
insertSort = function(arr, item)
lo = 0
hi = arr.len
while lo < hi
mid = floor((lo + hi) / 2)
ans = input("Is " + item + " less than " + arr[mid] + "? y/n: ")
ans = ans[0].lower
if ans == "y" then
hi = mid
else
lo = mid + 1
end if
end while
arr.insert(lo, item)
end function
items = "violet red green indigo blue yellow orange".split
ordered = []
for item in items
insertSort(ordered, item)
end for
print ordered
- Output:
Is red less than violet? y/n: y Is green less than violet? y/n: y Is green less than red? y/n: n Is indigo less than green? y/n: n Is indigo less than violet? y/n: y Is blue less than indigo? y/n: y Is blue less than green? y/n: n Is yellow less than blue? y/n: y Is yellow less than green? y/n: y Is yellow less than red? y/n: n Is orange less than blue? y/n: y Is orange less than yellow? y/n: y Is orange less than red? y/n: n ["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_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";
- 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.
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 cr
nest$ shuffle
dup witheach [ echo$ sp ] cr cr
sortwith askuser cr
witheach [ 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
Extra code was added to the REXX program to handle incorrectly formatted answers.
Also note that lists in REXX start with unity, not zero.
/*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
- 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 = 0
sortedItems = []
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 = 0
p 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
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)
- 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]
XPL0
include xpllib; \for Print
int Items, Size, I, J, Gap, JG, T, C, Count;
[Items:= ["violet", "red", "green", "indigo", "blue", "yellow", "orange"];
Size:= 7;
Count:= 0;
Gap:= Size>>1;
while Gap > 0 do
[for I:= Gap to Size-1 do
[J:= I - Gap;
loop [JG:= J + Gap;
Count:= Count+1;
Print("%2d: Is %6s less than %6s (y/n)? ",
Count, Items(J), Items(JG));
repeat OpenI(1);
C:= ChIn(1);
until C=^y or C=^n;
ChOut(0, C); CrLf(0);
if C = ^y then quit;
T:= Items(J); Items(J):= Items(JG); Items(JG):= T;
J:= J - Gap;
if J < 0 then quit;
];
];
Gap:= Gap>>1;
];
Print("The colors of the rainbow, in sorted order, are:\n");
for I:= 0 to Size-2 do Print("%s, ", Items(I));
Print("%s\n", Items(I));
]
- Output:
1: Is violet less than indigo (y/n)? n 2: Is red less than blue (y/n)? y 3: Is green less than yellow (y/n)? n 4: Is violet less than orange (y/n)? n 5: Is indigo less than orange (y/n)? n 6: Is orange less than red (y/n)? n 7: Is orange less than yellow (y/n)? y 8: Is yellow less than indigo (y/n)? y 9: Is indigo less than blue (y/n)? n 10: Is yellow less than blue (y/n)? y 11: Is indigo less than green (y/n)? n 12: Is blue less than green (y/n)? n 13: Is yellow less than green (y/n)? y 14: Is indigo less than violet (y/n)? y The colors of the rainbow, in sorted order, are: red, orange, yellow, green, blue, indigo, violet