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)In general, is there a pessimal (either in time or space) algorithm for any given problem, where there is provably no algorithm that is more reluctant (either in time or space)? Of course, without any cheating to waste resources (either in time or space). For example, calculating Fibonacci numbers recursively (without memoization): is this provably the slowest algorithm for Fibonacci numbers?