
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


Sort an array of composite structures by a key.



For example, if you define a composite structure that presents a name-value pair (in pseudo-code):

Define structure pair such that: 
   name as a string
   value as a string

and an array of such pairs:

   x: array of pairs

then define a sort routine that sorts the array x by the key name.

This task can always be accomplished with Sorting Using a Custom Comparator.

If your language is not listed here, please see the other article.




use framework "Foundation"
 
----- SORTING COMPOSITE STRUCTURES (BY MULTIPLE KEYS) ------
 
-- List of {strKey, blnAscending} pairs -> list of records -> sorted list of records
 
-- sortByComparing :: [(String, Bool)] -> [Record] -> [Record]
on sortByComparing(keyDirections, xs)
    set ca to current application
 
    script recDict
        on |λ|(x)
            ca's NSDictionary's dictionaryWithDictionary:x
        end |λ|
    end script
    set dcts to map(recDict, xs)
 
    script asDescriptor
        on |λ|(kd)
            set {k, d} to kd
            ca's NSSortDescriptor's sortDescriptorWithKey:k ascending:d selector:dcts
        end |λ|
    end script
 
    ((ca's NSArray's arrayWithArray:dcts)'s ¬
        sortedArrayUsingDescriptors:map(asDescriptor, keyDirections)) as list
end sortByComparing
 
 
--------------------------- TEST ---------------------------
on run
    set xs to [¬
        {city:"Shanghai ", pop:24.2}, ¬
        {city:"Karachi ", pop:23.5}, ¬
        {city:"Beijing ", pop:21.5}, ¬
        {city:"Sao Paulo ", pop:24.2}, ¬
        {city:"Dhaka ", pop:17.0}, ¬
        {city:"Delhi ", pop:16.8}, ¬
        {city:"Lagos ", pop:16.1}]
 
    -- Boolean true for ascending order, false for descending:
 
    sortByComparing([{"pop", false}, {"city", true}], xs)
end run
 
 
-------------------- GENERIC FUNCTIONS ---------------------
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map
 
 
-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn