## Pessimal Algorithms and Simplexity Analysis

### October 25, 2013

Here is our version of slowsort:

`(define (slowsort a i j)`

(when (< i j)

(let ((m (quotient (+ i j) 2)))

(slowsort a i m)

(slowsort a (+ m 1) j)

(when (> (vector-ref a m) (vector-ref a j))

(let ((t (vector-ref a m)))

(vector-set! a m (vector-ref a j))

(vector-set! a j t)))

(slowsort a i (- j 1))))))

I am amazed it actually works, as this example shows:

`> (define x (vector 4 6 7 1 5 2 3))`

> (slowsort x 0 6)

> x

#(1 2 3 4 5 6 7)

You can run the program at http://programmingpraxis.codepad.org/aYK2UmdY.

Advertisements

Pages: 1 2

Slowsort in Python.

Slowsort implementation in Racket.

Non-in-place and extracting minima instead of maxima. CoffeeScript. (Apparently there is no integer division in this language, whether flooring or another kind, but there are a number of “tricks” like x|0 to truncate an x.)

sort = (arr) ->

[arr, res] = [arr[0...arr.length], []]

while arr.length > 0

i = min(arr)

res.push(i)

k = arr.indexOf(i)

arr[k..k] = []

res

min = (arr) ->

if arr.length is 1 then arr[0]

else

a = sort(arr[0...arr.length/2|0])[0]

b = sort(arr[arr.length/2|0...arr.length])[0]

if a < b then a else b

`console.log(sort([3,1,4,1,5,9,2,6]))`

[…] find the index of a target x in a sorted array. We looked at a different algorithm that paper in a previous exercise. I’ll leave it to you to fetch the paper and enjoy the sincerity of the authors’ […]

In studying the slowsort algorithm, I realized that it is entirely to eager to move A[m] into place by swapping A[m] with A[j]. A better (i.e., worse) algorithm would swap A[m] with A[m+1], and repeat until A[m] is at the end of the list (like a bubble sort). Clearly the improved algorithm, which I call ‘slowersort’, is more pessimal.