#  select -- returns the Kth smallest value in an array.
#
#  Description:
#  ------------
#  The input array (size n) will be rearranged to have the value in location 
# arr[k], with all smaller elements moved to arr[1:k-1] (in arbitrary order) 
# and all larger elements in arr[k+1:n] (also in arbitrary order).
#  
#  Date		Author		Description
#  ----		------		-----------
#  31-Jul-1997  J.-C. Hsu	Modified from select in Numerical Recipes
#------------------------------------------------------------------------------

real procedure select (arr, n, k)

real	arr[ARB]	# input array
int	n		# size of input array
int	k		# kth smallest number to be selected

int	i, j, l, ir, mid
real	a, temp
#==============================================================================
begin
	l = 1
	ir = n
	
1	if (ir-l <= 1) {	# active partition contains 1 or 2 elements
	    if (ir-l == 1) {	# active partition contains 2 elements
		if (arr[ir] < arr[l]) {
		    temp = arr[l]
		    arr[l] = arr[ir]
		    arr[ir] = temp
		}
	    }
	    return (arr[k])
	} else {
	
	    # choose median of left, center, and right elements as partitioning
	    # element a.  Also rearrange so that arr[l+1] <= arr[l], 
	    # arr[ir] >= arr[l]
	    mid = (l+ir) / 2
	    temp = arr[mid]
	    arr[mid] = arr[l+1]
	    arr[l+1] = temp
	    if (arr[l+1] > arr[ir]) {
		temp = arr[l+1]
		arr[l+1] = arr[ir]
		arr[ir] = temp
	    }
	    if (arr[l] > arr[ir]) {
		temp = arr[l]
		arr[l] = arr[ir]
		arr[ir] = temp
	    }
	    if (arr[l+1] > arr[l]) {
		temp = arr[l+1]
		arr[l+1] = arr[l]
		arr[l] = temp
	    }
	    
	    # initialize pointers for partitioning
	    i = l + 1
	    j = ir

	    # partitioning element
	    a = arr[l]

	    # beginning of innermost loop
3	        i = i + 1		# scan up to find element > a
	    if (arr[i] < a) goto 3
4	    	j = j - 1		# scan down to find element < a
	    if (arr[j] > a) goto 4
	    if (j < i) goto 5		# pointers crossed.  exit with 
					# partitioning complete
	    # exchange elements
	    temp = arr[i]
	    arr[i] = arr[j]
	    arr[j] = temp
	    goto 3			# end of innermost loop

	    # insert partitioning element
5	    arr[l] = arr[j]
	    arr[j] = a

	    # keep active the partition that contains the kth element
	    if (j >= k) ir = j - 1
	    if (j <= k) l = i
	}
	goto 1
end