Category talk:ALGOL 68-sort

Source code

# sort.incl.a68: sorting related modes, operators, etc.                       #

    # mode to hold the array bounds for sorting a subset of the array         #
    MODE ELEMENTS = STRUCT( INT low, high );

    # swaps the values of a and b                                             #
    PRIO =:= = 9;
    OP   =:= = ( REF INT    a, b )REF INT:    BEGIN INT    t := b; b := a; a := t END;
    OP   =:= = ( REF REAL   a, b )REF REAL:   BEGIN REAL   t := b; b := a; a := t END;
    OP   =:= = ( REF STRING a, b )REF STRING: BEGIN STRING t := b; b := a; a := t END;

    # in-place quick sort a[ low OF bounds : high OF bounds ]                 #
    PRIO QUICKSORT = 9;
    OP   QUICKSORT = ( REF[]INT a, ELEMENTS bounds )REF[]INT:
         IF INT lb = low OF bounds, ub = high OF bounds;
            ub <= lb
         THEN a                         # at most 1 element - no need to sort #
         ELSE                           # more than one element, so must sort #
            INT left  := lb;
            INT right := ub;
            # choosing the middle element of the array as the pivot           #
            INT pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
            WHILE
                WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI
                DO
                    left  +:= 1
                OD;
                WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
                DO
                    right -:= 1
                OD;
                left <= right
            DO
                a[ left  ] =:= a[ right ];
                left       +:= 1;
                right      -:= 1
            OD;
            a QUICKSORT ELEMENTS( lb,   right );
            a QUICKSORT ELEMENTS( left, ub    )
         FI # QUICKSORT # ;
    OP   QUICKSORT = ( REF[]REAL a, ELEMENTS bounds )REF[]REAL:
         IF INT lb = low OF bounds, ub = high OF bounds;
            ub <= lb
         THEN a                         # at most 1 element - no need to sort #
         ELSE                           # more than one element, so must sort #
            INT left   := lb;
            INT right  := ub;
            # choosing the middle element of the array as the pivot           #
            REAL pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
            WHILE
                WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI
                DO
                    left  +:= 1
                OD;
                WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
                DO
                    right -:= 1
                OD;
                left <= right
            DO
                a[ left  ] =:= a[ right ];
                left       +:= 1;
                right      -:= 1
            OD;
            a QUICKSORT ELEMENTS( lb,   right );
            a QUICKSORT ELEMENTS( left, ub    );
            a
         FI # QUICKSORT # ;
    OP   QUICKSORT = ( REF[]STRING a, ELEMENTS bounds )REF[]STRING:
         IF INT lb = low OF bounds, ub = high OF bounds;
            ub <= lb
         THEN a                         # at most 1 element - no need to sort #
         ELSE                           # more than one element, so must sort #
            INT left  := lb;
            INT right := ub;
            # choosing the middle element of the array as the pivot           #
            STRING pivot := a[ left + ( ( right + 1 ) - left ) OVER 2 ];
            WHILE
                WHILE IF left  <= ub THEN a[ left  ] < pivot ELSE FALSE FI
                DO
                    left  +:= 1
                OD;
                WHILE IF right >= lb THEN a[ right ] > pivot ELSE FALSE FI
                DO
                    right -:= 1
                OD;
                left <= right
            DO
                a[ left  ] =:= a[ right ];
                left       +:= 1;
                right      -:= 1
            OD;
            a QUICKSORT ELEMENTS( lb,   right );
            a QUICKSORT ELEMENTS( left, ub    )
         FI # QUICKSORT # ;

    # quicksorts a in-place                                                   #
    OP   QUICKSORT = ( REF[]INT    a )REF[]INT:    a QUICKSORT ELEMENTS( LWB a, UPB a );
    OP   QUICKSORT = ( REF[]REAL   a )REF[]REAL:   a QUICKSORT ELEMENTS( LWB a, UPB a );
    OP   QUICKSORT = ( REF[]STRING a )REF[]STRING: a QUICKSORT ELEMENTS( LWB a, UPB a );


# end sort.incl.a68                                                           #