#!/usr/bin/newlisp

# heapsort - benchmark
#
# note, that newLISP has fast built-in sort and random algorithms
# not used in this - same way - benchmark
#

(set 'IM 139968)
(set 'IA 3877)
(set 'IC 29573)

(set 'LAST 42)

(define (gen_random maximum)
	(set 'LAST (mod (add (mul LAST IA) IC) IM))
	(div (mul maximum LAST) IM))

(define (heapsort n ra)
	(set 'rra 0 'i 0 'j 0)
	(set 'l (+ (>> n 1) 1))
	(set 'ir n)

	(while (not done)
		(if (> l 1) 
			(begin
				(dec 'l)
				(set 'rra (ra l)))
			(begin
				(set 'rra (ra ir))
				(nth-set ir ra (ra 1))
				(dec 'ir)
				(if (= ir 1)
					(begin
						(nth-set (ra 1) rra)
						(set 'done true)
						; return
						ra))))
		(set 'i l)
		(set 'j (<< l 1))
		(if (not done) (begin 
			(while (<= j ir)
				(if (and (< j ir) (< (ra j) (ra (+ j 1))))
					(inc ' j))
				(if (< rra (ra j))
					(begin
						(nth-set (ra i) (ra j))
						(set 'i j)
						(inc 'j i))
					(set 'j (+ ir 1))))
			(nth-set (ra i) rra))
		) ra))

(define (main)
	(set 'N (integer (last (main-args))))

	(set 'ary (array (+ N 1)))

	(for (i 1 N) (nth-set (ary i) (gen_random 1.0)))

	(set 'ary (heapsort N ary))

	(println (format "%.10f" (ary N)))
)

(main)
(exit)

;; eof

			
		
			
			


syntax highlighting with newLISP and syntax.cgi