
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.




DEFINE PTR="CARD"
DEFINE PAIR_SIZE="4"
DEFINE PAIR_COUNT="1"
 
TYPE Pair=[PTR name,value]
 
BYTE ARRAY pairs(100)
BYTE count=[0]
 
PTR FUNC GetItemAddr(INT index)
  PTR addr
 
  addr=pairs+index*PAIR_SIZE
RETURN (addr)
 
PROC PrintArray()
  INT i
  Pair POINTER p
 
  Put('[)
  FOR i=0 TO count-1
  DO
    IF i>0 THEN Put(' ) FI
    p=GetItemAddr(i)
    PrintF("(%S,%S)",p.name,p.value)
  OD
  Put(']) PutE()
RETURN
 
PROC Append(CHAR ARRAY n,v)
  Pair POINTER dst
 
  dst=GetItemAddr(count)
  dst.name=n
  dst.value=v
  count==+1
RETURN
 
PROC InitData()
  Append("Warsaw","Poland")
  Append("Prague","Czech Republic")
  Append("London","United Kingdom")
  Append("Paris","France")
  Append("Madrit","Spain")
  Append("Berlin","Germany")
  Append("Rome","Italy")
  Append("Moscow","Russia")
  Append("Budapest","Hungary")
RETURN
 
PROC Sort()
  INT i,j,minpos
  CHAR ARRAY tmp
  Pair POINTER p1,p2
 
  FOR i=0 TO count-2
  DO
    minpos=i
    FOR j=i+1 TO count-1
    DO
      p1=GetItemAddr(minpos)
      p2=GetItemAddr(j)
      IF SCompare(p1.name,p2.name)>0 THEN
        minpos=j
      FI
    OD
 
    IF minpos#i THEN
      p1=GetItemAddr(minpos)
      p2=GetItemAddr(i)
      tmp=p1.name p1.name=p2.name p2.name=tmp
      tmp=p1.value p1.value=p2.value p2.value=tmp
    FI
  OD
RETURN
 
PROC Main()
  InitData()
  PrintE("Array before sort:")
  PrintArray() PutE()
 
  Sort()
  PrintE("Array after sort:")
  PrintArray()
RETURN