Problem Statement

Write a program to find the   median   value of a vector of floating-point numbers. The program need not handle the case where the vector is empty, but must handle the case where there are an even number of elements.   In that case, return the average of the two middle values. There are several approaches to this.   One is to sort the elements, and then pick the element(s) in the middle. Sorting would take at least   O(n logn).   Another approach would be to build a priority queue from the elements, and then extract half of the elements to get to the middle element(s).   This would also take   O(n logn).   The best solution is to use the   selection algorithm   to find the median in   O(n)   time. Quickselect_algorithm

Let's start with the solution:

PROGRAM MEDIAN

DIM X[10]

PROCEDURE QUICK_SELECT
    LT=0 RT=L-1
    J=LT
    REPEAT
        PT=X[K]
        SWAP(X[K],X[RT])
        P=LT
        FOR I=P TO RT-1 DO
            IF X[I]
        END FOR
        SWAP(X[RT],X[P])
        IF P=K THEN EXIT PROCEDURE END IF
        IF P
        IF P>=K THEN RT=P-1 END IF
    UNTIL J>RT
END PROCEDURE

PROCEDURE MEDIAN
    K=INT(L/2)
    QUICK_SELECT
    R=X[K]
    IF L-2*INT(L/2)<>0 THEN R=(R+X[K+1])/2 END IF
END PROCEDURE

BEGIN
   PRINT(CHR$(12);) !CLS
   X[0]=4.4 X[1]=2.3 X[2]=-1.7 X[3]=7.5 X[4]=6.6 X[5]=0
   X[6]=1.9 X[7]=8.2 X[8]=9.3 X[9]=4.5 X[10]=-11.7
   L=11
   MEDIAN
   PRINT(R)
END PROGRAM