
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.




 
a = .array~new
 
a~append(.pair~new("06-07", "Ducks"))
a~append(.pair~new("00-01", "Avalanche"))
a~append(.pair~new("02-03", "Devils"))
a~append(.pair~new("01-02", "Red Wings"))
a~append(.pair~new("03-04", "Lightning"))
a~append(.pair~new("04-05", "lockout"))
a~append(.pair~new("05-06", "Hurricanes"))
a~append(.pair~new("99-00", "Devils"))
a~append(.pair~new("07-08", "Red Wings"))
a~append(.pair~new("08-09", "Penguins"))
 
b = a~copy   -- make a copy before sorting
b~sort
say "Sorted using direct comparison"
do pair over b
   say pair
end
 
c = a~copy
-- this uses a custom comparator instead
c~sortWith(.paircomparator~new)
say
say "Sorted using a comparator (inverted)"
do pair over c
   say pair
end
 
-- a name/value mapping class that directly support the sort comparisons
::class pair inherit comparable
::method init
  expose name value
  use strict arg name, value
 
::attribute name
::attribute value
 
::method string
  expose name value
  return name "=" value
 
-- the compareto method is a requirement brought in
-- by the
::method compareto
  expose name
  use strict arg other
  return name~compareto(other~name)
 
-- a comparator that shows an alternate way of sorting
::class pairComparator subclass comparator
::method compare
  use strict arg left, right
  -- perform the comparison on the names
  return -left~name~compareTo(right~name)
 