#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)

      (display to-sort)

      (display "\n")

      (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)))))