It's been a long time since the last /prog/ challenge. However, since then the board has filled up with stupid assignments and the return of FrozenVoid.
To level the challenge with current times, here's the proposal:
Design and implement a sorting algorithm with complexity O(nn). Lower complexities will not be allowed. Redundand or blatantly no-ops will not be allowed. Poster must provide proof of complexity.
Extra points will be awarded for a O(nnn) or for an INTERCAL implementation.
def nnsort(x): n = len(x); time.sleep(n ** n); return sorted(x)
Name:
Anonymous2011-11-30 18:46
This one here's O(n*n!):
import itertools
def issorted(N):
it = iter(N)
it.next()
return all(a <= b for a,b in itertools.izip(N, it))
def sort(N):
for Ns in itertools.permutations(N,len(N)):
if issorted(Ns):
return Ns
print(sort([3,6,2,1,9]))
Name:
Anonymous2011-11-30 18:55
Is there an algorithm that only sorts the output when time goes to infinity, so the sequences generated are only converging to the sorted sequence, or is that impossible given finite input?
I guess the problem with this is that formally a program that runs forever can't be considered a correct, because it never returns anything that can be verified.
(defun n^n-sort (list)
(let ((length (length list))
(new-list nil))
(dotimes (i length)
(push (elt list (random length)) new-list))
(if (and (same list new-list) (apply #'<= new-list))
new-list
(n^n-sort list))))
It's similar to Bogosort, except that instead of just shuffling the list, it takes random items without making sure that it gets each one and only gets each one once. So, for the same reason that Bogosort is O(n!) (it has a 1/n! chance of getting the list right) mine is O(n^n). Technically it's a little less if there are duplicates in the input list, though.
>>16
That binds i to the number of the current iteration, and no, you need it even if you don't actually use it. For example, (dotimes (i 3) (print i)) prints: 0
1
2
Name:
Anonymous2011-12-01 0:53
>>15
Actually, bogosort is O(infinite), since that's the worst case scenario and the average of it (with 1 as best) is still infinite ((infinite + 1) / 2 = infinite).