DEFINITION MODULE Sort; (*============================================================== Version : 2.0 16 Sep 1990 C. Lins Compiler : Generic pc Modula-2 Component: Tools - Sorting Utilities Unless stated otherwise, each of the sort algorithms assume the array being sorted has an index in the range of 0..N-1. Furthermore, the array itself extends from 0 through N, inclusive. a[N] is used by many of the below algorithms as a temporary. Refer to The Modula-2 Software Component Library, Volume 4, Chapter 3 for comprehensive analytic results on the performance of these algorithms. REVISION HISTORY v1.00 13-21 May 1989 C. Lins: Initial implementation v2.00 16 Sep 1990 C. Lins Created generic pc version (C) Copyright 1990 Charles A. Lins ==============================================================*) FROM Relations IMPORT (*--type*) Relation; (*--------------------*) (* The following procedure types declare operations on the components of an array given indices into the array. The client module must provide actual procedures necessary to implement these operations. The following semantics are assumed by the various sort algorithms: CompareProc compares the values of the elements at the given indices returning the ordering relation between them. Specifically, CompareProc returns the following result: less when A[i] < A[j] greater when A[i] > A[j] equal when A[i] = A[j] where A is the array, i indicates the first parameter, and j indicates the second parameter. AssignProc assigns the value of the element at the second index to the value of the element at the first index. This is equivalent to the Modula-2 language statement A[i] := A[j]. SwapProc swaps the elements at the given indices. Thus, the result is: A[i]' = A[j] and A[j]' = A[i] *) TYPE CompareProc = PROCEDURE (CARDINAL, CARDINAL) : Relation; TYPE AssignProc = PROCEDURE (CARDINAL, CARDINAL); TYPE SwapProc = PROCEDURE (CARDINAL, CARDINAL); (*--------------------*) PROCEDURE InsertionSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); swap : SwapProc (*--in *)); PROCEDURE BinaryInsertionSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); assign : AssignProc (*--in *)); PROCEDURE SelectionSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); swap : SwapProc (*--in *)); PROCEDURE ShellSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); assign : AssignProc (*--in *)); PROCEDURE HeapSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); swap : SwapProc (*--in *)); PROCEDURE QuickSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); assign : AssignProc (*--in *); swap : SwapProc (*--in *); cutoff : INTEGER (*--in *)); PROCEDURE BSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); assign : AssignProc (*--in *); swap : SwapProc (*--in *)); (* MeanSort is only suitable for sorting arrays whose keys are numeric quantities. This is because is uses the mean value of a sample of the array to perform the ordering of keys. In this particular version, we assume that the keys are INTEGERs. Thus, in addition to the usual comparison and swap procedure parameters, operations are necessary for extracting the numeric key and storing the computed mean at a specific array index. These operations are provided by the procedure types "ValueProc" and "AssignItemProc", respectively. *) TYPE ValueProc = PROCEDURE (CARDINAL) : INTEGER; TYPE AssignItemProc = PROCEDURE (CARDINAL, INTEGER); PROCEDURE MeanSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); swap : SwapProc (*--in *); value : ValueProc (*--in *); assign : AssignItemProc (*--in *)); (* StraightMerge sort assumes array indices in the range of 1..N instead of 0..N-1. The index positions N+1 to 2*N are used as temporaries for holding the intermediate result. *) PROCEDURE StraightMerge ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); assign : AssignProc (*--in *)); PROCEDURE BubbleSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); swap : SwapProc (*--in *)); PROCEDURE ShakerSort ( numItems : CARDINAL (*--in *); compare : CompareProc (*--in *); swap : SwapProc (*--in *)); END Sort.