[PC C++] need an inefficient sorting routine

[CompWiz]

So, I'm working on a project, and I need a deliberately inefficient sorting routine(don't ask). Basically, it needs to sort an array of 100 random positive integers. So, it needs to be able to sort 100 numbers of wildly varying sizes in a fairly reasonable amount of time(no more than say a few minutes) Apparently, that rules out a Bogosort, as it would take something like ~9.3x10^159 iterations [mod edit: replaced with scientific notation](I think, I really don't know about big O notation), or, perhaps an infinite amount, depending on the quality of the c++ random number generator, and the much faster quantum bogosort isn't really feasable

so, any ideas? a deliberatly and interestingly inefficient sort that will sort 100 random numbers in a few minutes. I was looking through this page, but it got a bit confusing. Or, maybe just a really obscure sort would do. Just as long as it's not something ordinary.

Thanks.

[kv83]

a few minutes for 100 random numbers... that's to slow... you can do that in less than a second

[blueskies]

why not use an efficient sorting routine and add a delay? probably easier than finding a slow sorting algo.

[CompWiz]

ok, lets say roughly 30 seconds. And no, I don't want to use a delay, it needs to be a real sorting routine that can sort the numbers, but it does it inefficiently, without using some delay. And it would be nice if it had some name, like "bogosort" or "stoogesort" do. Any ideas?

[Andy_J]

The worst actual deterministic sorting algorithm is bubblesort, and for 100 numbers that wouldn't take more than a few seconds. You're either going to have to add a delay or go with bogosort which can take anywhere from 1 iteration to infinite iterations.

I find it funny that the pseudocode for bogosort uses is_sorted as the termination condition.

[CompWiz]

how long would a bogosort take, on average, for 100 numbers? any really rough estimates? I would guess a really long time. But it isn't the only inefficient routine. Look on the wiki article about sorting, or the article I linked to.

Even if something has to work for just 10 seconds, that would be all right.


Hmm, what would be the fastest way to sort the numbers? Maybe a quicksort to begin with, and then an insertion sort after the groupings get down into the 8-20 size.

[Dwedit]

Sorry, but in these days of multi GHz PC's, there is no slow way to sort 100 numbers. With the ability to easily do 20 million operations on each N, you'd need to try extremely hard to find an ineffecient enough sort routine.

My suggestion: Write it in Actionscript, that lanugage is at least 100 times slower than QBasic.

[Andy_J]

You cannot give an average time for bogosort since it is random. You can only state the best-case scenario will be O(N), and the worst-case scenario will be O(infinity).

[Jim e]

A dumber version of bubble sort may be the slowest however with only 100 numbers it wouldn't take so long. hmmm....


how bout this

Code: Select all

    for(k=LOWESTKEY; k<HIGHESTKEY; k++) {
        for(i=1;i<=n;i++) {
            if (list[i]==k && list[i-1]>k) {
                list[i]=list[i-1];
                list[i-1]=k;
                i=1;
            }
        }
    }

LOWESTKEY is the lowest vaule in the list, HIGHESTKEY is the largest vaule, n is the length of the array and list is the array itself. Also k would be HIGHESTKEY-LOWESTKEY;

So what is that O[k*(n^2)/2], not sure but it should be pretty slow.

[coelurus]

Make a neural net that will have to figure out what to do in order to sort a list. That ought to take some time.

[tr1p1ea]

Hahaha, why does it have to be inefficient? Why cant you just have some wasted cycles or a delay?

[threefingeredguy]

Maybe he's comparing it to his own personal method and he wants it to look gooood.

[crzyrbl]

1. you could make it extremely graphical and add 3d effects
2. make a loop to calculate and step through pi. only go through an iteration in the sort every time the number's 1, 3, 3, and 7 pop up in a row.