[PC C++] need an inefficient sorting routine
Moderator: MaxCoderz Staff
[PC C++] need an inefficient sorting routine
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.
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.
In Memory of the Maxcoderz Trophy
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?
In Memory of the Maxcoderz Trophy
-
- Calc Master
- Posts: 1110
- Joined: Mon 20 Dec, 2004 10:01 pm
- Location: In the state of Roo Fearing
- Contact:
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.
I find it funny that the pseudocode for bogosort uses is_sorted as the termination condition.
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.
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.
In Memory of the Maxcoderz Trophy
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.
My suggestion: Write it in Actionscript, that lanugage is at least 100 times slower than QBasic.
You know your hexadecimal output routine is broken when it displays the character 'G'.
- Jim e
- Calc King
- Posts: 2457
- Joined: Sun 26 Dec, 2004 5:27 am
- Location: SXIOPO = Infinite lives for both players
- Contact:
A dumber version of bubble sort may be the slowest however with only 100 numbers it wouldn't take so long. hmmm....
how bout thisLOWESTKEY 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.
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;
}
}
}
So what is that O[k*(n^2)/2], not sure but it should be pretty slow.
-
- Calc King
- Posts: 2195
- Joined: Sun 27 Mar, 2005 4:06 am
- Location: sleeping
- Contact: