1

After reading this question and through the various Phone Book sorting scenarios put forth in the answer, I found the concept of the BOGO sort to be quite interesting. Certainly there is no use for this type of sorting algorithm but it did raise an interesting question in my mind-- could their be a sorting algorithm that is infinitely impossible to complete?

In other words, is there a process where one could attempt to compare and re-order a fixed set of data and can yet never achieve an actual sorted list?

This is much more of a theoretical/philosophical question than a practical one and if I was more of a mathematician I'd probably be able to prove/disprove such a possibility. Has anyone asked this question before and if so, what can be said about it?

Community
  • 1
  • 1
RLH
  • 15,230
  • 22
  • 98
  • 182

7 Answers7

4

[edit:] no deterministic process with a finite amount of state takes "O(infinity)" since the slowest it can be is to progress through all possible states. this includes sorting.

[earlier, more specific answer:] no. for a list of size n you only have state space of size n! in which to store progress (assuming that the entire state of the sort is stored in the ordering of the elements and it really is "doing something," deterministically).

so the worst possible behaviour would cycle through all available states before terminating and take time proportional to n! (at the risk of confusing matters, there must be a single path through the state - since that is "all the state" you cannot have a process move from state X to Y, and then later from state X to Z, since that requires additional state, or is non-deterministic)

andrew cooke
  • 45,717
  • 10
  • 93
  • 143
  • 1
    If the program is only allowed to use O(N) space and has no input or source of randomness other than the input data, your statement is true. On the other hand, who said the program was limited to using O(N) scratch space? – supercat Aug 04 '11 at 19:24
  • but then you open the question to "anything". for example: i define a sort to run a simulation of the entire universe and then do a quicksort. for the question to be focused, i think this restriction is necessary. but you could extend it to space proportional to n and still not have an "infinite" time; the basic argument doesn't change unless you have an "infinite" amount of scratch space. – andrew cooke Aug 04 '11 at 19:26
  • The way one rules out 'simulation of the entire universe' is to specify that execution must be completely deterministic with respect to the input data stream, which is of size N. There are a number of open problems which will terminate for some inputs but not for others, where there is no upper bound to the amount of storage that may be required before the algorithm terminates. What I don't know is whether there are any algorithms which are guaranteed to terminate for all inputs, but where the time and space required cannot be computed in bounded time. – supercat Aug 04 '11 at 19:43
  • ah, ok, yes that's a better approach (and i don't know either). well, it's easy to construct probabilistic ones, but i don't know of any deterministic ones. – andrew cooke Aug 04 '11 at 19:58
3

Idea 1:

function sort( int[] arr ) {
    int[] sorted = quicksort( arr ); // compare and reorder data
    while(true); // where'd this come from???
    return sorted; // return answer
}

Idea 2

How do you define O(infinity)? The formal definition of Big-O merely states that f(x)=O(g(x)) implies that M*g(x) is an upper bound of f(x) given sufficiently large x and some constant M.

Typically when you talking about "infinity", you are talking about some sort of unbounded limit. So in this case, the only reasonable definition is saying that O(infinity) is O(function that's larger than every function). Obviously a function that's larger than every function is an upper bound. Thus technically everything is "O(infinity)"

Idea 3

Assuming you mean theta notation (tight bound)...

If you impose the additional restriction that the algorithm is smart (returns when it finds a sorted permutation) and every permutation of the list must be visited in a finite amount of time, then the answer no. There are only N! permutations of a list. The upper bound for such a sorting algorithm is then a finite over finite numbers, which is finite.

tskuzzy
  • 35,812
  • 14
  • 73
  • 140
  • why do you need `quicksort` at all? – Vlad Aug 04 '11 at 19:22
  • @Vlad: In his problem statement, he asked for a sorting algorithm that "attempts to compare and re-order a fixed set of data" :) – tskuzzy Aug 04 '11 at 19:31
  • 1
    would you please define "attempt" more precisely? – Vlad Aug 04 '11 at 19:33
  • It's possible to design a sorting "algorithm" whose completion would be undecidable. For example, search for a set of integers a, b, c, d, n, such that a^n + b^n + c^n = d^n, and also such that the lower digits of n represent the input data, sorted. There'd be no bound to how much space such an algorithm could require if it completes at all. – supercat Aug 04 '11 at 19:48
  • +1 for Idea 2. For some reason you are the only one to note this. – Patrick Aug 05 '11 at 08:53
2

Your question doesn't really have much to do with sorting. An algorithm which is guaranteed never to complete would be pretty dull. Indeed, even an algorithm which would might or might not ever complete would be pretty dull. Much more interesting would be an algorithm which would be guaranteed to complete, eventually, but whose worst-case computation time with respect to the size of the input would not be expressible as O(F(N)) for any function F that could itself be computed in bounded time. My hunch would be that such an algorithm could be devised, but I'm not sure how.

supercat
  • 77,689
  • 9
  • 166
  • 211
1

How about this one:

  1. Start at the first item.
  2. Flip a coin.
  3. If it's heads, switch it with the next item.
  4. If it's tails, don't switch them.
  5. If list is sorted, stop.
  6. If not, move onto the next pair ...

It's a sorting algorithm -- the kind a monkey might do. Is there any guarantee that you'll arrive at a sorted list? I don't think so!

John
  • 15,990
  • 10
  • 70
  • 110
  • This is more of a sorting procedure than a sorting algorithm (no defined termination). I think a sorted list will occur with probability 1. The interesting part is detecting when you have one so you can stop. – Ted Hopp Aug 04 '11 at 19:23
  • This is pretty much the Bogosort algorithm the OP mentioned; it does in fact "almost surely" terminate (i.e. with P(sorted) == 1). – dlev Aug 04 '11 at 19:28
1

Yes -

SortNumbers(collectionOfNumbers)
{
  If IsSorted(collectionOfNumbers){
     reverse(collectionOfNumbers(1:end/2))     
  } 

  return SortNumbers(collectionOfNumbers)
}
YetAnotherUser
  • 9,156
  • 3
  • 39
  • 53
1
  Input:      A[1..n] : n unique integers in arbitrary order
  Output:     A'[1..n] : reordering of the elements of A
              such that A'[i] R(A') A'[j] if i < j.
  Comparator: a R(A') b iff A'[i] = a, A'[j] = b and i > j

More generally, make the comparator something that's either (a) impossible to reconcile with the output specification, so that no solution can exist, or (b) uncomputable (e.g., sort these (input, turing machine) pairs in order of the number of steps needed for the machine to halt on the input).

Even more generally, if you have a procedure that fails to halt on a valid input, the procedure is not an algorithm which solves the problem on that input/output domain... which means you don't have an algorithm at all, or that what you have is only an algorithm if you appropriately restrict the domain.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • Are there any algorithms which can be shown to terminate eventually, but whose worst-case running time and space requirements can be shown to be uncomputable in any form of bounded time? – supercat Aug 04 '11 at 19:51
0

Let's suppose that you have a random coin flipper, infinite arithmetic, and infinite rationals. Then the answer is yes. You can write a sorting algorithm which has 100% chance of successfully sorting your data (so it really is a sorting function), but which on average will take infinite time to do so.

Here is an emulation of this in Python.

# We'll pretend that these are true random numbers.
import random
import fractions

def flip ():
    return 0.5 < random.random()

# This tests whether a number is less than an infinite precision number in the range
# [0, 1].  It has a 100% probability of returning an answer.
def number_less_than_rand (x):
    high = fractions.Fraction(1, 1)
    low = fractions.Fraction(0, 1)

    while low < x and x < high:
        if flip():
            low = (low + high) / 2
        else:
            high = (low + high) / 2

    return high < x

def slow_sort (some_array):
    n = fractions.Fraction(100, 1)
    # This loop has a 100% chance of finishing, but its average time to complete
    # is also infinite.  If you haven't studied infinite series and products, you'll
    # just have to take this on faith.  Otherwise proving that is a fun exercise.
    while not number_less_than_rand(1/n):
        n += 1
    print n
    some_array.sort()
btilly
  • 43,296
  • 3
  • 59
  • 88