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.

About these ads

Pages: 1 2

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

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 )

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

Follow

Get every new post delivered to your Inbox.

Join 622 other followers

%d bloggers like this: