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.
Slowsort in Python.
def slowsort(L): n = len(L) if n == 1: return L mid = n // 2 mx = max(slowsort(L[:mid])[-1], slowsort(L[mid:])[-1]) L.remove(mx) return slowsort(L) + [mx]Slowsort implementation in Racket.
#lang racket (define (slow-sort! v [i 0] [j (vector-length v)]) (cond [(<= (- j i) 1) v] [else (define k (quotient (+ j i) 2)) (slow-sort! v i k) (slow-sort! v k j) (define max-a (vector-ref v (- k 1))) (define max-b (vector-ref v (- j 1))) (vector-set! v (- k 1) (min max-a max-b)) (vector-set! v (- j 1) (max max-a max-b)) (slow-sort! v i (- j 1))]))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.
def slowersort(awry, i=None, j=None): if i is None: i = 0 if j is None: j = len(awry) - 1 if i < j: m = (i + j) // 2 slowersort(awry, i, m) slowersort(awry, m + 1, j) if awry[m] > awry[j]: for k in range(m, j): awry[k], awry[k + 1] = awry[k + 1], awry[k] slowersort(awry, i, j - 1) awry = list('hgfedcba') print(awry) slowersort(awry) print(awry)