
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.




BEGIN
 
    CLASS COMPARABLE;;
 
    COMPARABLE CLASS PAIR(N,V); TEXT N,V;;
 
    CLASS COMPARATOR;
    VIRTUAL:
        PROCEDURE COMPARE IS
            INTEGER PROCEDURE COMPARE(A, B); REF(COMPARABLE) A, B;;
    BEGIN
    END**OF**COMPARATOR;
 
    COMPARATOR CLASS PAIRBYNAME;
    BEGIN
        INTEGER PROCEDURE COMPARE(A, B); REF(COMPARABLE) A, B;
        BEGIN
            COMPARE := IF A QUA PAIR.N < B QUA PAIR.N THEN -1 ELSE
                       IF A QUA PAIR.N > B QUA PAIR.N THEN +1 ELSE 0;
        END;
    END**OF**PAIRBYNAME;
 
    PROCEDURE BUBBLESORT(A, C); NAME A; REF(COMPARABLE) ARRAY A; REF(COMPARATOR) C;
    BEGIN
       INTEGER LOW, HIGH, I;
       BOOLEAN SWAPPED;
 
       PROCEDURE SWAP(I, J); INTEGER I, J;
       BEGIN
           REF(COMPARABLE) TEMP;
           TEMP :- A(I); A(I) :- A(J); A(J) :- TEMP;
       END**OF**SWAP;
 
       LOW := LOWERBOUND(A, 1);
       HIGH := UPPERBOUND(A, 1);
       SWAPPED := TRUE;
       WHILE SWAPPED DO
       BEGIN
           SWAPPED := FALSE;
           FOR I := LOW + 1 STEP 1 UNTIL HIGH DO
           BEGIN
               COMMENT IF THIS PAIR IS OUT OF ORDER ;
               IF C.COMPARE(A(I - 1), A(I)) > 0 THEN
               BEGIN
                   COMMENT SWAP THEM AND REMEMBER SOMETHING CHANGED ;
                   SWAP(I - 1, I);
                   SWAPPED := TRUE;
               END;
           END;
       END;
    END**OF**BUBBLESORT;
 
    COMMENT ** MAIN PROGRAM **;
    REF(PAIR) ARRAY A(1:5);
    INTEGER I;
 
    A(1) :- NEW PAIR( "JOE", "5531" );
    A(2) :- NEW PAIR( "ADAM", "2341" );
    A(3) :- NEW PAIR( "BERNIE", "122" );
    A(4) :- NEW PAIR( "WALTER", "1234" );
    A(5) :- NEW PAIR( "DAVID", "19" );
 
    BUBBLESORT(A, NEW PAIRBYNAME);
 
    FOR I:= 1 STEP 1 UNTIL 5 DO
    BEGIN OUTTEXT(A(I).N); OUTCHAR(' '); OUTTEXT(A(I).V); OUTIMAGE; END;
    OUTIMAGE;
 
END.