;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;                               SORTING (with graphics !!!)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(define (make-random-list n)
  (let ((l '()))
    (do ((i n (- i 1))) ((= i 0) (randomise l))
      (set! l (cons i l)))))

(define (make-random-vector n)
  (let ((l (make-random-list n))
	(v (make-vector n)))
    (do ((i 0 (+ i 1))) ((= i n) v)
      (vector-set! v i (list-ref l i)))))

(define (plot-vector v m)
  (let* ((n (vector-length v))
	 (inc (quotient 400 n)))
    (do ((i 0 (+ i 1))) ((= i n))
      (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 2))))

(define (compare p i j v m)
  (let* ((r (p (vector-ref v i) (vector-ref v j)))
	 (c (cond (r 4) (#t 3))))
    (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 4)
    (draw-box 1 (+ 1 (* m j)) (+ 1 (* m (vector-ref v j))) 4)
    (draw-line (+ 1 (* m i)) (+ 1 (* m (vector-ref v i)))
	       (+ 1 (* m j)) (+ 1 (* m (vector-ref v j))) c)
    (draw-line (+ 1 (* m i)) (+ 1 (* m (vector-ref v i)))
	       (+ 1 (* m j)) (+ 1 (* m (vector-ref v j))) 0)
    (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 2)
    (draw-box 1 (+ 1 (* m j)) (+ 1 (* m (vector-ref v j))) 2)
    r))

(define (swap v i j m)
  (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 0)
  (draw-box 1 (+ 1 (* m j)) (+ 1 (* m (vector-ref v j))) 0)
  (let ((temp (vector-ref v i)))
    (vector-set! v i (vector-ref v j))
    (vector-set! v j temp))
  (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 2)
  (draw-box 1 (+ 1 (* m j)) (+ 1 (* m (vector-ref v j))) 2))
;;;
;;; Given vector v, swap the ith element with the jth element
;;; NOTE: and keep a count of number of swaps performed
;;;

(define (i-bubble-sort v p)
  (let* ((n (vector-length v))
	 (m (quotient 400 n)))
    (clear) (plot-vector v m)
    (do ((i (- n 1) (- i 1)))
	((= i 0))
      (do ((j 0 (+ j 1)))
	  ((= j i))
	(cond ((compare p (+ j 1) j v m)
	       (swap v j (+ j 1) m))))
      (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 4))))
;;;
;;; Bubble sort
;;;


(define (locate v lwb upb p m)
  (let ((loc-e lwb))
    (do ((i (+ 1 lwb) (+ i 1))) ((> i upb) loc-e)
      (cond ((compare p loc-e i v m)
	     (set! loc-e i))))))

(define (i-selection-sort v p)
  (let* ((n (vector-length v))
	 (m (quotient 400 n)))
    (clear) (plot-vector v m)
    (do ((i (- n 1) (- i 1))) ((< i 0))
      (let ((j (locate v 0 i p m)))
	(swap v i j m))
      (draw-box 1 (+ 1 (* m i)) (+ 1 (* m (vector-ref v i))) 4))))

(define (bubble-demo n)
  (let ((n (inexact->exact n)))
    (cond ((> n 400) (set! n 400))
	  ((< n 1) (set! n 10)))
    (i-bubble-sort (make-random-vector n) <)))

(define (selection-demo n)
  (let ((n (inexact->exact n)))
    (cond ((> n 400) (set! n 400))
	  ((< n 1) (set! n 10)))
    (i-selection-sort (make-random-vector n) <)))

(define (draw-position v i m colour)
  (draw-rectangle (* m (vector-ref v i))
		  m
		  (+ 10 (* 3 m i))
		  220  colour))

(define (draw-vector v m)
  (let* ((n (vector-length v)))
    (do ((i 0 (+ i 1))) ((= i n))
      (draw-position v i m 4))))

(define (box-swap v i j m)
  (draw-position v i m 0)
  (draw-position v j m 0)
  (let ((temp (vector-ref v i)))
    (vector-set! v i (vector-ref v j))
    (vector-set! v j temp))
  ;(do ((i 1 (+ i 1))) ((> i 1000)))
  (draw-position v i m 2)
  (draw-position v j m 2))
;;;
;;; Given vector v, swap the ith element with the jth element
;;;

(define (i-box-bubble-sort v p)
  (let* ((n (vector-length v))
	 (m (quotient 200 n)))
    (clear) (draw-vector v m)
    (do ((i (- n 1) (- i 1)))
	((= i 0))
      (do ((j 0 (+ j 1)))
	  ((= j i))
	(draw-position v j m 4)
	(cond ((p (vector-ref v (+ j 1)) (vector-ref v j))
	       (box-swap v j (+ j 1) m))))
      (draw-position v i m 3))
    (draw-position v 0 m 3)))
;;;
;;; Bubble sort
;;;

(define (box-bubble-demo n)
  (let ((n (inexact->exact n)))
    (cond ((> n 100) (set! n 100))
	  ((< n 20) (set! n 20)))
    (i-box-bubble-sort (make-random-vector n) <)))

(print 

"************************************************************

You have just loaded the graphical demo for two sorting algorithms,
namely bubble sort and selection sort. To run a demo on bubble sort

     (bubble-demo n)

also see ...

     (box-bubble-demo n)

... and to run a demo on selection sort

    (selection-demo n)

... where n is the size of the data set to be sorted and 0 < n < 401

")

;(display "<<Hit RETURN to continue>>") (read-line) (read-line)

(print
"
A vector v of size n is created, and initially (vector-set! v i i)
for all i. That is, the ith vector element is set to the
value i. The contents are then shuffled.

We can then plot the vector v such that i is the x coordinate
and (vector-ref v i) is the y coordinate. If the vector v is sorted
then we get a straight line (diagonal). Initially,
things will look like a scatter plot. As the search algorithm proceeds
we see order emerging, from scatter to a straight line!!!

In bubble sort we scan up to i, swap adjacent elements that are out
of place. On each swap I undraw the items that are about to be swapped
and then redraw them. You will see points drifting into the straight line.
You should also see order emerging within the partially sorted
part of the vector.

")
(display "<<Hit RETURN to continue>>") (read-line)

(print
"
In selection sort, we find the largest element in the vector, get its
positiuon, and swap with position n. We then decrement n. In this case we will
see a fast growing line.

Please now make a call to (bubble-demo 100) and then (selection-demo 100)

PS: Please also have a look at (box-bubble-demo 50) for a different
    view of bubble sort!!! In the box-bubble-demo I've represented
    numbers to be sorted by boxes of that size. You will then see
    boxes being shuffled about, int order. Again I use colour
    to show when a box is in its final sorted position

*******************************************************")