
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


The numerical rank of competitors in a competition shows if one is better than, equal to, or worse than another based on their results in a competition.

The numerical rank of a competitor can be assigned in several different ways.



Task

The following scores are accrued for all competitors of a competition (in best-first order):

44 Solomon
42 Jason
42 Errol
41 Garry
41 Bernard
41 Barry
39 Stephen
For each of the following ranking methods, create a function/method/procedure/subroutine... that applies the ranking method to an ordered list of scores with scorers:

 Standard. (Ties share what would have been their first ordinal number).
 Modified. (Ties share what would have been their last ordinal number).
 Dense. (Ties share the next available integer). 
 Ordinal. ((Competitors take the next available integer. Ties are not treated otherwise).
 Fractional. (Ties share the mean of what would have been their ordinal numbers).


See the wikipedia article for a fuller description.

Show here, on this page, the ranking of the test scores under each of the numbered ranking methods.




(*
    The five ranking methods are implemented here as script objects sharing inherited code rather than as simple
    handlers, although there appears to be little advantage either way. This way needs fewer lines of code
    but more lines of explanatory comments!
*)
use AppleScript version "2.4" -- Mac OS 10.11 (Yosemite) or later (for these 'use' commands).
use sorter : script "Custom Iterative Ternary Merge Sort" -- <https://macscripter.net/viewtopic.php?pid=194430#p194430>
 
script standardRanking
    -- Properties and handlers inherited or overridden by the other script objects.
    -- The 'references' are to values that won't be available until 'results' is set to a list.
    -- 'me' and 'my' refer to the script object using the code at the time.
    property results : missing value
    property startIndex : 1
    property endIndex : a reference to length of (a reference to results)
    property step : 1
    property currentRank : missing value
    property currentScore : missing value
 
    -- Main handler.
    on resultsFrom(theScores)
        copy theScores to my results
        -- The task description specifies that the input list is already ordered, but that's not assumed here.
        -- Additionally, competitors with equal scores are arranged alphabetically by name.
        -- The comparer here is 'me' because the current script object contains the isGreater(a, b) handler to be used.
        tell sorter to sort(my results, my startIndex, my endIndex, {comparer:me})
        set my currentScore to score of item (my startIndex) of my results
        set my currentRank to my startIndex's contents
        repeat with i from (my startIndex) to (my endIndex) by (my step)
            my rankResult(i)
        end repeat
        -- Since these script objects are assigned to top-level variables in a running script, make sure the potentially
        -- long 'results' list isn't saved back to the script file with them at the end of the run. This precaution isn't
        -- necessary in a library script or if the scripts are instantiated and assigned to local variables at run time.
        set localVariable to my results
        set my results to missing value
        return localVariable
    end resultsFrom
 
    -- Comparison handler used by the sort. The returned boolean indicates whether or not record 'a' should go after record 'b'.
    on isGreater(a, b)
        if (a's score is less than b's score) then return true
        return ((a's score is equal to b's score) and (a's competitor comes after b's competitor))
    end isGreater
 
    -- Specialist ranking handler. Inherited by the modifiedRanking script, but overridden by the others.
    on rankResult(i)
        set thisResult to item i of my results
        set thisScore to thisResult's score
        if (thisScore is not currentScore) then
            set my currentRank to i
            set my currentScore to thisScore
        end if
        set item i of my results to thisResult & {rank:my currentRank}
    end rankResult
end script
 
script modifiedRanking -- Uses the standardRanking code, but works backwards through the results list.
    property parent : standardRanking
    property startIndex : a reference to length of (a reference to results)
    property endIndex : 1
    property step : -1
end script
 
script denseRanking
    property parent : standardRanking
 
    on rankResult(i)
        set thisResult to item i of my results
        set thisScore to thisResult's score
        if (thisScore is not my currentScore) then
            set my currentRank to (my currentRank) + 1
            set my currentScore to thisScore
        end if
        set item i of my results to thisResult & {rank:my currentRank}
    end rankResult
end script
 
script ordinalRanking
    property parent : standardRanking
 
    on rankResult(i)
        set item i of my results to (item i of my results) & {rank:i}
    end rankResult
end script
 
script fractionalRanking
    property parent : standardRanking
 
    on rankResult(i)
        set thisResult to item i of my results
        set thisScore to thisResult's score
        if (thisScore is not my currentScore) then
            -- i and currentRank are simultaneously indices and ranks.
            -- The average of any run of consecutive integers is that of the first and last.
            set average to (i - 1 + (my currentRank)) / 2
            repeat with j from (my currentRank) to (i - 1)
                set rank of item j of my results to average
            end repeat
            set my currentRank to i
            set my currentScore to thisScore
        end if
        set item i of my results to thisResult & {rank:i as real}
    end rankResult
end script
 
-- Task code:
on formatRankings(type, theResults)
    set rankings to {type}
    repeat with thisResult in theResults
        set end of rankings to (thisResult's rank as text) & tab & thisResult's competitor & " (" & thisResult's score & ")"
    end repeat
 
    return joinStrings(rankings, linefeed)
end formatRankings
 
on joinStrings(listOfText, delimiter)
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to delimiter
    set output to listOfText as text
    set AppleScript's text item delimiters to astid
 
    return output
end joinStrings
 
local theScores, output
set theScores to {{score:44, competitor:"Solomon"}, {score:42, competitor:"Jason"}, {score:42, competitor:"Errol"}, ¬
    {score:41, competitor:"Garry"}, {score:41, competitor:"Bernard"}, {score:41, competitor:"Barry"}, ¬
    {score:39, competitor:"Stephen"}}
set output to {}
set end of output to formatRankings("Standard ranking:", standardRanking's resultsFrom(theScores))
set end of output to formatRankings("Modified ranking:", modifiedRanking's resultsFrom(theScores))
set end of output to formatRankings("Dense ranking:", denseRanking's resultsFrom(theScores))
set end of output to formatRankings("Ordinal ranking:", ordinalRanking's resultsFrom(theScores))
set end of output to formatRankings("Fractional ranking:", fractionalRanking's resultsFrom(theScores))
return joinStrings(output, linefeed & linefeed)