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[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]))

  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?

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: