
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.




 
{def H.sort
 {def H.sort.i
  {lambda {:f :x :a}
   {if {A.empty? :a}
    then {A.new :x}
    else {if {:f :x {A.first :a}}
    then {A.addfirst! :x :a}
    else {A.addfirst! {A.first :a} {H.sort.i :f :x {A.rest :a}}} }}}}
 {def H.sort.r
  {lambda {:f :a1 :a2}
   {if {A.empty? :a1}
    then :a2 
    else {H.sort.r :f {A.rest :a1} {H.sort.i :f {A.first :a1} :a2}} }}}
 {lambda {:f :a}
  {H.sort.r :f :a {A.new}} }}
-> H.sort
 
{def H.display
 {lambda {:h}
  {table
   {tr {S.map {{lambda {:h :i} {td {car {A.get :i :h}}}} :h}
              {S.serie 0 {- {A.length :h} 1}}}}
   {tr {S.map {{lambda {:h :i} {td {cdr {A.get :i :h}}}} :h}
              {S.serie 0 {- {A.length :h} 1}}}}
}}}
-> H.display
 
1) an array of pairs:
{def H {A.new {cons Joe 5531}
              {cons Adam 2341}
              {cons Bernie 122} 
              {cons Walter 1234}
              {cons David 19}}}
-> H
 
2) display sorted by names:
{H.display
 {H.sort {lambda {:a :b} {< {lexicographic {car :a} {car :b}} 0}} {H}}}
-> 
Adam 	Bernie 	David 	Joe 	Walter
 2341 	122 	19 	5531 	1234
 
3) display sorted by values:
{H.display
 {H.sort {lambda {:a :b} {< {cdr :a} {cdr :b}}} {H}}}
-> 
David 	Bernie 	Walter 	Adam 	Joe
 19 	122 	1234 	2341 	5531
 