-2
\$\begingroup\$

The Golf (re)Sort

Our favourite place

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.

\$\endgroup\$

closed as off-topic by William Barbosa, user80551, user16402, Martin Ender, ProgramFOX Jul 22 '14 at 6:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – William Barbosa, user80551, Community, Martin Ender, ProgramFOX
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ It should be Big-Omega instead of Big-O, since e.g. mergesort is in O(n!). \$\endgroup\$ – fabian Jul 21 '14 at 23:09
  • 1
    \$\begingroup\$ You should make it more clear in your question that the score is based on the algorithmic complexity of the answers. stackoverflow.com/a/12338937/1275256 \$\endgroup\$ – gxtaillon Jul 22 '14 at 0:30
  • 2
    \$\begingroup\$ This a a code-bowling problem, except with algorithmic complexity rather than number of characters. I suspect it will run into the same pitfalls. You need to be more precise with what you consider a useless operation, and what "closer" means in "Every operation needs to bring you closer to the goal of a sorted list." \$\endgroup\$ – xnor Jul 22 '14 at 4:02
  • 1
    \$\begingroup\$ There's one in a [code-trolling] question that has a C sorting program of O(n!...!) with the factorial repeated n times. Can't find it. \$\endgroup\$ – Ming-Tang Jul 22 '14 at 6:57
  • 1
    \$\begingroup\$ A fair few of the answers to codegolf.stackexchange.com/q/20478/194 could be reposted as is, so this is at best borderline for being a dupe. \$\endgroup\$ – Peter Taylor Jul 22 '14 at 8:40
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't this just be n^n? \$\endgroup\$ – SuperJedi224 Oct 26 '15 at 19:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.