How do I write a sort worse than O(n!)

Question

I wrote an O(n!) sort for my amusement that can't be trivially optimized to run faster without replacing it entirely. [And no, I didn't just randomize the items until they were sorted].

How might I write an even worse Big-O sort, without just adding extraneous junk that could be pulled out to reduce the time complexity?

http://en.wikipedia.org/wiki/Big_O_notation has various time complexities sorted in growing order.

Edit: I found the code, here is my O(n!) deterministic sort with amusing hack to generate list of all combinations of a list. I have a slightly longer version of get_all_combinations that returns an iterable of combinations, but unfortunately I couldn't make it a single statement. [Hopefully I haven't introduced bugs by fixing typos and removing underscores in the below code]

def mysort(somelist):
    for permutation in get_all_permutations(somelist):
        if is_sorted(permutation):
            return permutation

def is_sorted(somelist):
    # note: this could be merged into return... something like return len(foo) <= 1 or reduce(barf)
    if (len(somelist) <= 1): return True
    return 1 > reduce(lambda x,y: max(x,y),map(cmp, somelist[:-1], somelist[1:]))

def get_all_permutations(lst):
    return [[itm] + cbo for idx, itm in enumerate(lst) for cbo in get_all_permutations(lst[:idx] + lst[idx+1:])] or [lst]

Answer 1

Chris and I mentioned Bozosort and Bogosort in a different question.

Answer 2

One way that I can think of would be to calculated the post position of each element through a function that vary gradually moved the large elements to the end and the small ones to the beginning. If you used a trig based function, you could make the elements osculate through the list instead of going directly toward their final position. After you've processed each element in the set, then do a full traversal to determine if the array is sorted or not.

I'm not positive that this will give you O(n!) but it should still be pretty slow.

Answer 3

There's always NeverSort, which is O(∞):

def never_sort(array)
  while(true)
  end
  return quicksort(array)
end

PS: I really want to see your deterministic O(n!) sort; I can't think of any that are O(n!), but have a finite upper bound in classical computation (aka are deterministic).

PPS: If you're worried about the compiler wiping out that empty while block, you can force it not to by using a variable both in- and outside the block:

def never_sort(array)
  i=0
  while(true) { i += 1 }
  puts "done with loop after #{i} iterations!"
  return quicksort(array)
end

Answer 4

I think that if you do lots of copying then you can get a "reasonable" brute force search (N!) to take N^2 time per case giving N!*N^2

Answer 5

There's a (proven!) worst sorting algorithm called slow sort that uses the “multiply and surrender” paradigm and runs in exponential time.

While your algorithm is slower, it doesn't progress steadily but instead performs random jumps. Additionally, slow sort's best case is still exponential while yours is constant.

Answer 6

How about looping over all arrays t of n integers (n-tuples of integers are countable, so this is doable though it's an infinite loop of course), and for each of these:

• if its elements are exactly those of the input array (see algo below!) and the array is sorted (linear algo for example, but I'm sure we can do worse), then return t;
• otherwise continue looping.

To check that two arrays a and b of length n contain the same elements, how about the following recursive algorithm: loop over all couples (i,j) of indices between 0 and n-1, and for each such couple

• test if a[i]==b[j]:
• if so, return TRUE if and only if a recursive call on the lists obtained by removing a[i] from a and b[j] from b returns TRUE;
• continue looping over couples, and if all couples are done, return FALSE.

The time will depend a lot on the distribution of integers in the input array.

Seriously, though, is there a point to such a question?

Edit:

@Jon, your random sort would be in O(n!) on average (since there are n! permutations, you have probability 1/n! of finding the right one). This holds for arrays of distinct integers, might be slightly different if some elements have multiple occurences in the input array, and would then depend on the distribution of the elements of the input arrays (in the integers).

Answer 7

You could always do a Random sort. It works by rearranging all the elements randomly, then checking to see if it's sorted. If not, it randomly resorts them. I don't know how it would fit in big-O notation, but it will definitely be slow!

Answer 8

Here is the slowest, finite sort you can get:

Link each operation of Quicksort to the Busy Beaver function.

By the time you get >4 operations, you'll need up-arrow notation :)