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

About these ads

Pages: 1 2

5 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])
        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]
             (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)
          k = arr.indexOf(i)
          arr[k..k] = []

    min = (arr) ->
       if arr.length is 1 then arr[0]
          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


  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')

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 666 other followers

%d bloggers like this: