Order by pair comparisons: Difference between revisions
(Added Wren) |
(→{{header|Raku}}: Added Raku solution) |
||
Line 203: | Line 203: | ||
red orange yellow green blue indigo violet</pre> |
red orange yellow green blue indigo violet</pre> |
||
=={{header|Raku}}== |
|||
Raku's sort (like most languages) can take a custom "comparator" routine. |
|||
Since the calls to the comparator are minimized, and the info that the user provides is analogous to the required return values of the comparator, we just need to embed the prompt directly in the comparator. |
|||
<lang perl6>my $ask_count = 0; |
|||
sub by_asking ( $a, $b ) { |
|||
$ask_count++; |
|||
constant $fmt = '%2d. Is %-6s [ less than | greater than | equal to ] %-6s? ( < = > ) '; |
|||
constant %o = '<' => Order::Less, |
|||
'=' => Order::Same, |
|||
'>' => Order::More; |
|||
loop { |
|||
my $input = prompt sprintf $fmt, $ask_count, $a, $b; |
|||
return $_ with %o{ $input.trim }; |
|||
say "Invalid input '$input'"; |
|||
} |
|||
} |
|||
my @colors = <violet red green indigo blue yellow orange>; |
|||
my @sorted = @colors.sort: &by_asking; |
|||
say (:@sorted); |
|||
die if @sorted».substr(0,1).join ne 'roygbiv'; |
|||
my $expected_ask_count = @colors.elems * log(@colors.elems); |
|||
warn "Too many questions? ({:$ask_count} > {:$expected_ask_count})" if $ask_count > $expected_ask_count;</lang> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
Revision as of 17:43, 14 April 2021
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.
Factor
Asking the user for an ordering specifier inside a custom comparator:
<lang factor>USING: formatting io kernel math.order prettyprint qw sorting ;
qw{ violet red green indigo blue yellow orange } [ "Is %s > %s? (y/n) " printf readln "y" = +gt+ +lt+ ? ] sort .</lang>
- Output:
Is violet > red? (y/n) y Is green > indigo? (y/n) n Is blue > yellow? (y/n) y Is red > green? (y/n) n Is violet > green? (y/n) y Is violet > indigo? (y/n) y Is yellow > orange? (y/n) y Is red > orange? (y/n) n Is green > orange? (y/n) y Is green > yellow? (y/n) y Is green > blue? (y/n) n Is indigo > blue? (y/n) y { "red" "orange" "yellow" "green" "blue" "indigo" "violet" }
Julia
<lang julia>const nrequests = [0] const ordering = Dict("violet" => 7, "red" => 1, "green" => 4, "indigo" => 6, "blue" => 5,
"yellow" => 3, "orange" => 2)
function tellmeifgt(x, y)
nrequests[1] += 1 while true print("Is $x greater than $y? (Y/N) => ") s = strip(readline()) if length(s) > 0 (s[1] == 'Y' || s[1] == 'y') && return true (s[1] == 'N' || s[1] == 'n') && return false end end
end
function orderbypair!(a::Vector)
incr = div(length(a), 2) while incr > 0 for i in incr+1:length(a) j = i tmp = a[i] while j > incr && tellmeifgt(a[j - incr], tmp) a[j] = a[j-incr] j -= incr end a[j] = tmp end if incr == 2 incr = 1 else incr = floor(Int, incr * 5.0 / 11) end end return a
end
const words = String.(split("violet red green indigo blue yellow orange", r"\s+")) println("Unsorted: $words") println("Sorted: $(orderbypair!(words)). Total requests: $(nrequests[1]).")
</lang>
- Output:
Is violet greater than indigo? (Y/N) => y Is red greater than blue? (Y/N) => n Is green greater than yellow? (Y/N) => y Is violet greater than orange? (Y/N) => y Is indigo greater than orange? (Y/N) => y Is orange greater than red? (Y/N) => n Is red 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) => n Is green greater than violet? (Y/N) => n Sorted: ["orange", "red", "yellow", "blue", "indigo", "green", "violet"]. Total requests: 12.
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
Uses binary search to insert successive items into a growing ordered list. Comparisons are asked for.
<lang python>def _insort_right(a, x, q):
""" Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. """
lo, hi = 0, len(a) while lo < hi: mid = (lo+hi)//2 q += 1 less = input(f"{q:2}: IS {x:>6} LESS-THAN {a[mid]:>6} ? y/n: ").strip().lower() == 'y' if less: hi = mid else: lo = mid+1 a.insert(lo, x) return q
def order(items):
ordered, q = [], 0 for item in items: q = _insort_right(ordered, item, q) return ordered, q
if __name__ == '__main__':
items = 'violet red green indigo blue yellow orange'.split() ans, questions = order(items) print('\n' + ' '.join(ans))</lang>
- Output:
1: IS red LESS-THAN violet ? y/n: y 2: IS green LESS-THAN violet ? y/n: y 3: IS green LESS-THAN red ? y/n: n 4: IS indigo LESS-THAN green ? y/n: n 5: IS indigo LESS-THAN violet ? y/n: y 6: IS blue LESS-THAN indigo ? y/n: y 7: IS blue LESS-THAN green ? y/n: n 8: IS yellow LESS-THAN blue ? y/n: y 9: IS yellow LESS-THAN green ? y/n: y 10: IS yellow LESS-THAN red ? y/n: n 11: IS orange LESS-THAN blue ? y/n: y 12: IS orange LESS-THAN yellow ? y/n: y 13: IS orange LESS-THAN red ? y/n: n red orange yellow green blue indigo violet
Raku
Raku's sort (like most languages) can take a custom "comparator" routine. Since the calls to the comparator are minimized, and the info that the user provides is analogous to the required return values of the comparator, we just need to embed the prompt directly in the comparator.
<lang perl6>my $ask_count = 0; sub by_asking ( $a, $b ) {
$ask_count++; constant $fmt = '%2d. Is %-6s [ less than | greater than | equal to ] %-6s? ( < = > ) '; constant %o = '<' => Order::Less, '=' => Order::Same, '>' => Order::More;
loop { my $input = prompt sprintf $fmt, $ask_count, $a, $b; return $_ with %o{ $input.trim }; say "Invalid input '$input'"; }
}
my @colors = <violet red green indigo blue yellow orange>; my @sorted = @colors.sort: &by_asking; say (:@sorted);
die if @sorted».substr(0,1).join ne 'roygbiv'; my $expected_ask_count = @colors.elems * log(@colors.elems); warn "Too many questions? ({:$ask_count} > {:$expected_ask_count})" if $ask_count > $expected_ask_count;</lang>
- Output:
1. Is violet [ less than | greater than | equal to ] red ? ( < = > ) > 2. Is green [ less than | greater than | equal to ] indigo? ( < = > ) < 3. Is blue [ less than | greater than | equal to ] yellow? ( < = > ) > 4. Is red [ less than | greater than | equal to ] green ? ( < = > ) < 5. Is violet [ less than | greater than | equal to ] green ? ( < = > ) > 6. Is violet [ less than | greater than | equal to ] indigo? ( < = > ) > 7. Is yellow [ less than | greater than | equal to ] orange? ( < = > ) > 8. Is red [ less than | greater than | equal to ] orange? ( < = > ) < 9. Is green [ less than | greater than | equal to ] orange? ( < = > ) > 10. Is green [ less than | greater than | equal to ] yellow? ( < = > ) > 11. Is green [ less than | greater than | equal to ] blue ? ( < = > ) < 12. Is indigo [ less than | greater than | equal to ] blue ? ( < = > ) > sorted => [red orange yellow green blue indigo violet]
Wren
<lang ecmascript>import "/ioutil" for Input import "/fmt" for Fmt
// Inserts item x in list a, and keeps it sorted assuming a is already sorted. // If x is already in a, inserts it to the right of the rightmost x. var insortRight = Fn.new{ |a, x, q|
var lo = 0 var hi = a.count while (lo < hi) { var mid = ((lo + hi)/2).floor q = q + 1 var prompt = Fmt.swrite("$2d: Is $6s less than $6s ? y/n: ", q, x, a[mid]) var less = Input.option(prompt, "yn") == "y" if (less) { hi = mid } else { lo = mid + 1 } } a.insert(lo, x) return q
}
var order = Fn.new { |items|
var ordered = [] var q = 0 for (item in items) { q = insortRight.call(ordered, item, q) } return ordered
}
var items = "violet red green indigo blue yellow orange".split(" ") var ordered = order.call(items) System.print("\nThe colors of the rainbow, in sorted order, are:") System.print(ordered)</lang>
- Output:
1: Is red less than violet ? y/n: y 2: Is green less than violet ? y/n: y 3: Is green less than red ? y/n: n 4: Is indigo less than green ? y/n: n 5: Is indigo less than violet ? y/n: y 6: Is blue less than indigo ? y/n: y 7: Is blue less than green ? y/n: n 8: Is yellow less than blue ? y/n: y 9: Is yellow less than green ? y/n: y 10: Is yellow less than red ? y/n: n 11: Is orange less than blue ? y/n: y 12: Is orange less than yellow ? y/n: y 13: Is orange less than red ? y/n: n The colors of the rainbow, in sorted order, are: [red, orange, yellow, green, blue, indigo, violet]