## 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.

Pages: 1 2

### 6 Responses to “Pessimal Algorithms and Simplexity Analysis”

1. Paul said

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]
```
2. 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))]))
```
3. Jussi Piitulainen said

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    else       a = sort(arr[0...arr.length/2|0])       b = sort(arr[arr.length/2|0...arr.length])       if a < b then a else b ```

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

4. […] 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’ […]

5. Mike said

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)
```
6. Daniel Forgues said

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?