'***************************************************** '* Calculate the median value of an array with the * '* Heapsort Method * '* ------------------------------------------------- * '* REFERENCE: * '* "NUMERICAL RECIPES By W.H. Press, B.P. Flannery, * '* S.A. Teukolsky and W.T. Vetterling, Cambridge * '* University Press, 1986" [BIBLI 08]. * '* * '* Basic Version By J-P Moreau * '* (www.jpmoreau.fr) * '* ------------------------------------------------- * '* SAMPLE RUN: * '* * '* Table to be sorted: * '* * '* 925 518 215 447 948 405 23 886 809 398 * '* 195 651 451 251 477 78 389 472 774 291 * '* 942 885 157 143 623 57 183 766 576 888 * '* 22 145 143 903 128 398 938 58 426 674 * '* 32 88 269 845 104 711 628 417 671 226 * '* 266 324 763 298 871 538 639 991 386 652 * '* 408 331 19 874 680 952 672 92 576 624 * '* 760 936 735 712 676 14 163 847 367 731 * '* * '* Median Value: 474.5 * '* * '* Sorted table (Heapsort method): * '* * '* 14 19 22 23 32 57 58 78 88 92 * '* 104 128 143 143 145 157 163 183 195 215 * '* 226 251 266 269 291 298 324 331 367 386 * '* 389 398 398 405 408 417 426 447 451 472 * '* 477 518 538 576 576 623 624 628 639 651 * '* 652 671 672 674 676 680 711 712 731 735 * '* 760 763 766 774 809 845 847 871 874 885 * '* 886 888 903 925 936 938 942 948 952 991 * '* * '***************************************************** DEFINT I-N DIM A(100) 'Table to be sorted CLS N = 80'initialize size of table TMAXVALUE = 1000 'initialize random generator RANDOMIZE TIMER 'generate random table of numbers (from 0 to TMAXVALUE) FOR i = 1 TO N A(i) = TMAXVALUE * RND(1) NEXT i PRINT PRINT " Table to be sorted:" GOSUB 2000 'call TWRIT(N,A) 'call MDIAN subroutine GOSUB 1500 'call MDIAN(A,N,AMED) PRINT PRINT " Median Value: "; AMED PRINT : PRINT PRINT " Sorted table (Heapsort method):" GOSUB 2000 'call TWRIT(N,A) PRINT END '***************************************************** '* Sorts an array A of length N in ascending order * '* by the Heapsort method * '* ------------------------------------------------- * '* INPUTS: * '* N size of table A * '* A table to be sorted * '* OUTPUT: * '* A table sorted in ascending order * '* * '* NOTE: The Heapsort method is a N Log2 N routine, * '* and can be used for very large arrays. * '***************************************************** 1000 'Subroutine HPSORT(N, A) 'Labels: 10, 20 L = N / 2 + 1 IR = N '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. 10 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 20 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 20 END IF A(i) = RRA GOTO 10 END '******************************************************* '* Given an array A of N numbers, returns their median * '* value AMED. The array A is modified and returned * '* sorted in ascending order. * '******************************************************* 1500 'Subroutine MDIAN(A, N, AMED) 'N2:Integer GOSUB 1000 'call HPSORT(N,A) N2 = N / 2 IF 2 * N2 = N THEN AMED = .5 * (A(N2) + A(N2 + 1)) ELSE AMED = A(N2 + 1) END IF RETURN 'write table of size N to standard output 2000 'SUBROUTINE TWRIT(N,A) F\$ = " ####" PRINT FOR i = 1 TO N PRINT USING F\$; A(i); IF INT(i / 10) = i / 10 THEN PRINT NEXT i RETURN 'end of file tmdian.bas