## Two Bad Sorts

### May 17, 2011

Both of these sorts are simple to code. We begin with stooge sort:

`(define (stooge-sort lt? xv . args)`

(if (null? args) (stooge-sort lt? xv 0 (- (vector-length xv) 1))

(let ((lo (car args)) (hi (cadr args)))

(when (lt? (vector-ref xv hi) (vector-ref xv lo))

(let ((t (vector-ref xv lo)))

(vector-set! xv lo (vector-ref xv hi))

(vector-set! xv hi t)))

(when (< 1 (- hi lo))

(let ((mid (quotient (- hi lo -1) 3)))

(stooge-sort lt? xv lo (- hi mid))

(stooge-sort lt? xv (+ lo mid) hi)

(stooge-sort lt? xv lo (- hi mid))))))

xv)

We used a vector instead of a list because it is more convenient to pass subscripts than to repeatedly take slices of lists. Bogosort is even simpler:

`(define (sorted? lt? xs)`

(cond ((null? xs) #t)

((null? (cdr xs)) #t)

((lt? (cadr xs) (car xs)) #f)

(else (sorted? lt? (cdr xs)))))

`(define (bogosort lt? xs)`

(if (sorted? lt? xs) xs

(bogosort lt? (shuffle xs))))

Our `sorted?`

is generic; if we limited ourselves to sorting integers, we could have said `(apply < xs)`

and done away with `sorted?`

.

Bogosort uses `rand`

/`randint`

and `shuffle`

from the Standard Prelude. You can run both sorts at http://programmingpraxis.codepad.org/tmpDUJnJ.

My Haskell solution (see http://bonsaicode.wordpress.com/2011/05/17/programming-praxis-two-bad-sorts/ for a version with comments):

Here’s my python version. Although it is worth noting it’s not very efficient, and bogo can easy cause a stack error.

My Python version:

My

`bogosort`

is iterative, so it avoids the Python recursion limit. For a few comments and tests, see github.In Ruby …

set $VERBOSE to true to watch the stooge sort work.

`(define (stooge! vec #!optional (start 0) (end (1- (vector-length vec))))`

(when (> (vector-ref vec start)

(vector-ref vec end))

(let ((tmp (vector-ref vec start)))

(vector-set! vec start (vector-ref vec end))

(vector-set! vec end tmp)))

(unless (or (= end start) (= 1 (- end start)))

(let* ((len (- end start))

(two-thirds (floor (* 2/3 len)))

(one-third (- len two-thirds)))

(stooge! vec start (+ start two-thirds))

(stooge! vec (+ start one-third) end)

(stooge! vec start (+ start two-thirds)))))

;

(define (sorted? vec)

(fold-left

(lambda (r x)

(if (and r (>= x r)) x #f))

(vector-ref vec 0)

(vector->list vec)))

;

(define (shuffle l)

(if (pair? l)

(if (zero? (random-integer 2))

(cons (car l) (shuffle (cdr l)))

(shuffle (append (cdr l) (list (car l)))))

'()))

;

(define (bogo! vec)

(when (not (sorted? vec))

(let ((i 0))

(map (lambda (x)

(vector-set! vec i x)

(set! i (1+ i)))

(shuffle (vector->list vec))))

(bogo! vec)))

My try in REXX:

[…] post: Two Bad Sorts « Programming Praxis Categories: Programming 0 Comments Tags: a-version-with, control, haskell, programming, […]

(define (sorted? lt? l)

(cond ((or (null? l) (null? (cdr l))) #t)

((not (lt? (car l) (cadr l))) #f)

(else (sorted? lt? (cdr l)))))

(define (bogo-sort l)

(if (sorted? <= l)

l (bogo-sort (shuffle l))))

(define (stooge-sort l)

(define (stooge-sort-impl v lo hi)

(define (swap! i j)

(let ((t (vector-ref v i)))

(vector-set! v i (vector-ref v j))

(vector-set! v j t)))

(if (and (>= (- hi lo) 1) (< (vector-ref v hi) (vector-ref v lo)))

(swap! lo hi))

(if (>= (- hi lo) 2)

(let ((m (floor (/ (- hi lo -1) 3))))

(stooge-sort-impl v lo (- hi m))

(stooge-sort-impl v (+ lo m) hi)

(stooge-sort-impl v lo (- hi m)))))

(let ((v (list->vector l)))

(stooge-sort-impl v 0 (- (length l) 1))

(vector->list v)))

Bogosort implementation in java: https://gist.github.com/1253001