#lang scheme

;; A implementation of Bogosort(http://en.wikipedia.org/wiki/Bogosort) in Scheme (plt-scheme)
;; Uses the "modern" version of Fisher-Yates shuffle for shuffling..(http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)
;;
;;
;;Amit Saha (http://amitksaha.wordpress.com; amitsaha.in@gmail.com)
;;
;;
;;
(define flag 0)

(define (bogosort to-sort)
  (if (eq? #t (sorted? to-sort))
    to-sort
     (begin
      (set! flag 0)
     (bogosort (shuffle to-sort)))))

(define (sorted? to-sort)
      (for ((i (in-range (- (vector-length to-sort) 1))))
	   (if (> (vector-ref to-sort i) (vector-ref to-sort (+ 1 i)))
	     (set! flag 1)
	     (set! flag flag)))
    (if (eq? 0 flag)
      #t
      #f))


;; Fisher-Yates shuffle
(define (shuffle deck)
  (let loop ((n (vector-length deck)) (shuff_deck deck))
    (if (<= n 1)
      shuff_deck
      (begin 
	(set! n (- n 1))
	(let* ([rand (random (+ 1 n))]
	       [tmp (vector-ref shuff_deck rand)]
	       )
	  (vector-set! shuff_deck rand (vector-ref shuff_deck n))
	  (vector-set! shuff_deck n tmp))
	(loop n shuff_deck)))))