## Two Bad Sorts

### May 17, 2011

We have some fun today implementing two really bad sorting algorithms.

*Stooge sort* is a recursively-defined algorithm that sorts *n* items in *O*(*n*^{log 3 / log 1.5}) comparisons: If the value at the end of the list is less than the value at the start of the list swap them. Then, if there are three are more items in the list, recursively sort the first two-thirds of the items in the list, then the last two-thirds of the items in the list, and finally (again) the first two-thirds of the items in the list. This is so bad that it takes a few seconds just to convince yourself that it actually works.

*Bogosort* is particularly bad, with factorial time complexity, on average, and no guarantee that it ever terminates: collect the items in the list in random order. If they are sorted, return them, otherwise try again with a new random ordering of the items in the list.

Your task is to implement stooge sort and bogosort. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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