-4
\$\begingroup\$

This question already has an answer here:

All good coders know some good sorting algorithms like quicksort or merge sort. There is also slow sorting algorithms, e.g. bubble sort and insertion sort.

But those are such easy to implement and so, so efficient. Too efficient. Your task is to create very slow sorting algorithm.

Please attach the Big O notation of your algorithm to your post to help us rate them. Also, please describe how your sorting algorithm works.

Input given trough STDIN. The first line contains number of arguments, and arguments are given after that. The arguments are integers in range from 0 to 105 and there are maximum 103 of them.

Output is list sorted and printed line by line into STDOUT sorted beginning from decending order.

You may not use any random numbers or any other random sources.

This is .

\$\endgroup\$

marked as duplicate by Peter Taylor, Optimizer, NinjaBearMonkey, Martin Ender, manatwork Jan 14 '15 at 14:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    \$\begingroup\$ What stops me from sorting the array again and again , say, n^n times to increase the Big O ? \$\endgroup\$ – Optimizer Jan 14 '15 at 13:07
  • \$\begingroup\$ That depends... bogosort has a good best case. How exactly will this be counted? \$\endgroup\$ – Tally Jan 14 '15 at 13:11
  • 1
    \$\begingroup\$ @MartinBüttner Bogobogosort \$\endgroup\$ – dwana Jan 14 '15 at 13:17
  • \$\begingroup\$ I just now saw that you could not use any random numbers or sources so I quess we can't shuffle either \$\endgroup\$ – dwana Jan 14 '15 at 13:30
  • 1
    \$\begingroup\$ You want to sort integers slowly? Why not use sleep sort? If that's still too fast for you then you make the sleep unit years! Or centuries! \$\endgroup\$ – Sp3000 Jan 14 '15 at 13:39
6
\$\begingroup\$

Mathematica, Time complexity O(n * n!), Space complexity O(n!)

list = RandomInteger[10, 7]
(*{5, 5, 4, 10, 5, 10, 5}*)
permutations = Permutations@list;
Cases[permutations, l_ /; And @@ Thread[Most[RotateLeft@l - l] >= 0]][[1]]
(*{4, 5, 5, 5, 5, 10, 10}*)

This generates all permutations, discards all that aren't sorted, and then picks the first one.

Therefore, it will use O(n!) memory and O(n!) time to generate all the permutations. Then it will use O(n!) time again, to iterate through the permutations, while needing O(n) for each of them to check that they are sorted.

Note that this is both the worst case and best case complexity.

\$\endgroup\$
0
\$\begingroup\$

CJam, Time complexity O(n(2n+1)*log(n)), Space complexity O(n)

q~:Q,_#2#{Q$;}*Q$p

This sorts the array n2n + 1 times using Merge Sort which has time complexity of n log(n)

But really, this can be extended to any time complexity with a final output in range of Big Integer.

(Don't) try it online here

Input is like:

[1 4 2 3 1 5 6 1 2344 343 1 2 3 23 1 2 32 1 2 3 4]

and output is the sorted array

A graph comparing n * n! with n2n + 1 * log(n)

\$\endgroup\$

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