
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:

O(n logn) sorts
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.


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]