The Golf (re)Sort

Question

The Golf (re)Sort

Everyone is sorting arrays these days, and so do we at our day jobs. But we like to go out golfing. When we do, we sure like to take our time. It is important to have a stress free experience.

Since we like golfing so much, we have decided to make a sorting algorithm that will let us stay away from the desk as much as possible. We decided to make Golf (re)Sort, a sorting algorithm that takes as time long as possible to complete. This way we can spend more time doing what we like the most, golfing.

---

The task is easy: Sort an array of integers using an algorithm that takes as long time, and has as high O-notation, as possible.

The rules:

• The algorithm must be deterministic. Thus you may not use randomness in the algorithm (so no bogosort)
• You may not use any un-productive operations or loops. Eg.: sleep 2, for i<n; i++ {/*no-op*/}, Open("www.the_internet.com").download. Every operation needs to bring you closer to the goal of a sorted list. An example would be to simply reverse the array for no other reason than reversing the array to increase the Ω-notation.

Provide:

• Name of the language
• The code
• An explanation to the approach + Ω(Big-Omega)-notation (lower bound).

Scoring:

Scoring will be done by looking at the Ω-runtime. The higher the better.

---

Example:

Language: Ruby

Code:

a = [6,9,7,5,7,90,9,6,4,32,9,7,4,223]
sorted = []

while a.count > 0
    min = [Float::INFINITY, -1]
    a.each_with_index do |e,i|
        min = [e,i] if e < min[0]
    end
    sorted << min[0]
    a.delete_at(min[1])
end

puts sorted.to_s

This is a variation on selection sort which have runtime of Ω(n^2). It is slow because it scans the array for the lowest value, then pushes that to the result array. It then deletes the value from the original array and starts over.

Answer 1

Python

def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

def sort(lst):
    newlst = []
    while len(lst) > 0:
        a, i = min([(ackermann(n, n), i) for i, n in enumerate(lst)])
        newlst.append(lst[i])
        del lst[i]
    return newlst

Uses Ackermann function to slow things down. That may qualify as unproductive...

Use example:

print sort([3, 1, 2, 3, 0]) # --> [0, 1, 2, 3, 3]

It actually works quite well for numbers between 0 and 3. (Note that it's destructive and only works for non-negative integers.)

Runtime - I'm not quite sure.

Answer 2

k4 (100)

  {{if[y<z;.z.s[x]'[y,m+1;(m:_(y+z)%2),z];if[(x m)>x z;@[x;z,m;:;x m,z]];.z.s[x;y;z-1]]}[x;0](#. x)-1}

This is a fairly straightforward (i.e. not particularly golfed) implementation of slowsort.

Here's a sample run, with timing information in milliseconds (the \t instruction):

  s:{{if[y<z;.z.s[x]'[y,m+1;(m:_(y+z)%2),z];if[(x m)>x z;@[x;z,m;:;x m,z]];.z.s[x;y;z-1]]}[x;0](#. x)-1}
  l:100?1000
  \t s`l
4270

The paper (v.s.) claims that the last few paragraphs of section 5 contain a proof of the running time of the algo, but I can't make heads or tails of it; all I know is that 4.2 seconds to sort 100 ints is pretty slow.

(I should also note that this implementation is an in-place sort, as given in the paper, which is why the list to sort is passed by name, rather than by value. This is rather strongly contrary to the functional programming principles of k4/q, but it was easier than figuring out a proper functional version.)

Answer 3

Python

This one isn't golfed, because I'm not much of a code golfer yet.

def sorted(l):
    for i in range(1, len(l)):
        if l[i] < l[i-1]:
            return False
    return True

class T:
    def __init__(self,l1,l2):
        self.l1 = l1
        self.l2 = l2
        self.children = []

    def build(self):
        if len(self.l2) == 0:
            return
        else:
            for i in range(0, len(self.l2)):
                nl1 = self.l1[:]
                nl2 = self.l2[:]
                nl1.append(self.l2[i])
                nl2.pop(i)
                child = T(nl1, nl2)
                child.build()
                self.children.append(child)

    def find_sorted(self):
        if len(self.l2) == 0:
            if sorted(self.l1):
                return self.l1
            return None
        result = None
        for child in self.children:
            if child.find_sorted() is not None:
                result = child.find_sorted()
        return result


def sort(l):
    tree = T([],l)
    tree.build()
    return tree.find_sorted()

Been a while since I took any classes so I'm trying to think of how to word the complexity. I know the number of nodes in the tree can be calculated with:

def numberOfNodes(n):
    if n==0:
        return 1
    return 1 + n * numberOfNodes(n - 1)

It builds this entire tree and searches through every node. So for a list size grows very fast:

0       1
1       2
2       5
3       16
4       65
5       326
6       1957
7       13700
8       109601
9       986410
10      9864101

If searching every node is cheating I can change that.

A list of 9 elements took about 6 seconds, and a list of 10 elements ran out of memory (used at least 1.9 GB of ram before it chickened out 25 seconds in).

Answer 4

Python, Omega(n^(n+2))

def sort(a):
    for i in xrange(len(a)**len(a)):
        b = list(a)
        for j in range(len(a)):
            k = i / len(a)**j % len(a)
            b[0], b[k] = b[k], b[0]
        if all(b[x] <= b[y] for x in range(len(a)) for y in range(x, len(a))):
            return b

Tries all possible orderings (and then some), returning only if the array is sorted. Uses Omega(n^2) to test if it's sorted, just to add insult to injury.