'********************************************************** '* Demonstration Program of In-place Merge Sorting * '* (about n * log(n) comparisons used with moderate * '* extra storage). * '* ------------------------------------------------------ * '* Reference: After a java algorithm By Jason Harrison, * '* 1995 University of British Columbia. * '* * '* Basic Version By J-P Moreau, Paris. * '* (www.jpmoreau.fr) * '* ------------------------------------------------------ * '* SAMPLE RUN: * '* * '* Initial table A: * '* 4.00 3.00 1.00 67.00 55.00 8.00 0.00 4.00 * '* -5.00 37.00 7.00 4.00 2.00 9.00 1.00 -1.00 * '* * '* Sorted table A: * '* -5.00 -1.00 0.00 1.00 1.00 2.00 3.00 4.00 * '* 4.00 4.00 7.00 8.00 9.00 37.00 55.00 67.00 * '* * '********************************************************** 'Program MSORT DEFDBL A-H, O-Z DEFINT I-N n = 16 n2 = n / 2 DIM A(n), tmp(n2) DIM hi AS INTEGER A(1) = 4: A(2) = 3: A(3) = 1: A(4) = 67 A(5) = 55: A(6) = 8: A(7) = 0: A(8) = 4 A(9) = -5: A(10) = 37: A(11) = 7: A(12) = 4 A(13) = 2: A(14) = 9: A(15) = 1: A(16) = -1 CLS PRINT PRINT " Initial table A:" FOR I = 1 TO n PRINT USING "####.##"; A(I); IF I = 8 THEN PRINT NEXT I lo = 1: hi = n GOSUB 2000 'call sort(A,1, n) PRINT PRINT PRINT " Sorted table A:" FOR I = 1 TO n PRINT USING "####.##"; A(I); IF I = 8 THEN PRINT NEXT I PRINT END '***************************************************** '* Sorts an array A of length N in ascending order * '* by the Heapsort method * '* ------------------------------------------------- * '* INPUTS: * '* N1 size of table RA * '* A table to be sorted * '* OUTPUT: * '* A table sorted in ascending order * '* * '* NOTE: The Heapsort method is a N Log N routine, * '* and can be used for very large arrays. * '* ------------------------------------------------- * '* REFERENCE: * '* "NUMERICAL RECIPES by W.H. Press, B.P. Flannery, * '* S.A. Teukolsky and W.T. Vetterling, Cambridge * '* University Press, 1986". * '***************************************************** 1000 'SUBROUTINE HPSORT(N1,A) L = n1 / 2 + 1 IR = n1 'The index L will be decremented from its initial value during the '"hiring" (heap creation) phase. Once it reaches 1, the index IR 'will be decremented from its initial value down to 1 during the '"retirement-and-promotion" (heap selection) phase. 1010 IF L > 1 THEN L = L - 1 RRA = A(L) ELSE RRA = A(IR) A(IR) = A(1) IR = IR - 1 IF IR = 1 THEN A(1) = RRA RETURN END IF END IF I = L J = L + L 1020 IF J <= IR THEN IF J < IR THEN IF A(J) < A(J + 1) THEN J = J + 1 END IF IF RRA < A(J) THEN A(I) = A(J) I = J: J = J + J ELSE J = IR + 1 END IF GOTO 1020 END IF A(I) = RRA GOTO 1010 RETURN '****************************************************** '* In-place sorting of a table a in ascending order * '* -------------------------------------------------- * '* Inputs: * '* a : Table of n real numbers * '* lo: Starting index (>=0) * '* hi: Ending index (<=n-1), with lo= hi THEN RETURN 'no action mid = (lo + hi) / 2 'Partition the list into two lists and sort them with heapsort '(to avoid a recursive call of sort). n1 = mid GOSUB 1000 'call hpsort(mid,A) FOR I = lo TO mid tmp(I) = A(I) A(I) = A(mid + I) NEXT I GOSUB 1000 'call hpsort(mid,A(mid + 1)) FOR I = lo TO mid A(mid + I) = A(I) A(I) = tmp(I) NEXT I 'Merge the two sorted lists starthi = mid + 1 endlo = mid WHILE lo <= endlo AND starthi <= hi IF A(lo) < A(starthi) THEN lo = lo + 1 ELSE ' a(lo) >= a(starthi) ' The next element comes from the second list, ' move the a[starthi] element into the next ' position and shuffle all the other elements up. T = A(starthi) FOR k = starthi - 1 TO lo STEP -1 A(k + 1) = A(k) NEXT k A(lo) = T lo = lo + 1 endlo = endlo + 1 starthi = starthi + 1 END IF WEND RETURN 'end of file msort.bas