I have to take back some of the mean things I've said about Intelligent Design creationism. They have finally made a significant contribution to a science…in this case, computer science. Behold the awesome power of the Intelligent Design Sort!
Intelligent Design Sort
Introduction
Intelligent design sort is a sorting algorithm based on the theory of intelligent design.
Algorithm Description
The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.
Analysis
This algorithm is constant in time, and sorts the list in-place, requiring no additional memory at all. In fact, it doesn't even require any of that suspicious technological computer stuff. Praise the Sorter!
Feedback
Gary Rogers writes:
Making the sort constant in time denies the power of The Sorter. The Sorter exists outside of time, thus the sort is timeless. To require time to validate the sort dimishes the role of the Sorter. Thus... this particular sort is flawed, and can not be attributed to 'The Sorter'.Heresy!
It's a kind of universal argument, too — just replace the word "list" with "gene", and it transforms into their usual assertion about biology.
- Log in to post comments
After being bitten by the Weasel I think the denizens of UD and Iders in general would do well to leave any computer programs alone.
I thought this was real at first.
Hmm. I was expecting:
THIS IS AN ALGORITHM.
See it doesn't change! Proof that God did it right the first time!
Aww I had an < algorithm> fail.
Wow, a sorting algorithm of O(1)! The best we have ever gotten is O(n log(n)). Amazing!
Funny, though if the sort transcends human understanding, then it is not very useful as we then can't write a program to search it effectively.
You and your metaphysical need to write useful programs...tsk, tsk.
Photoshop is too complex to have evolved.
Therefore: god.
I don't NEED to write useful programs... infinite loops are fun!
Wait
What?
When did they come up with an actual testable theory?
2+2=chair
This is better than O(1). It's O(0). Praise the Lord!
Real generalized sorts are O(N * lg(N)), but for certain inputs there are faster algorithms, such as O(N). Imagine taking the numbers 1...100 and shaking them out of order. To sort them does not even require looking at the items, you can just generate a new sorted list.
Dangermouse is one of the coolest cartoons ever so anyone with that URL automatically is cool.
Lawl. I should totally use that when people ask me to apply a sort on a set of data. "Oh, I'm using a new sort algorithm..."
Yeah, it is possible to get near O(n) with insertion sort if the data is already nearly sorted. Still, if it's not nearly sorted, it's O(n^2). The really nice algorithms that get O(n*log(n)) tend to fall apart with small data sets horribly. And Quick Sort dies at super large data sets due to recursing to death. If you took the time to implement a non-recursive version, though...
But the ID sort takes the same amount of time to sort no matter what, so it beats them all! (And manages to be just as useless as the real ID)
You had me going there for a second thinking it could be something real out of the Disc. Inst. Good thing I checked the rest of the DM website. The sad thing though is that here where I work and live, if I posted that link, most people would actually think it is the real thing. We have such a way to go battling ignorance.
But hey, reading that was fun.
Best, and keep on blogging.
While we're on creationists, just to let everyone know:
This year the North American Paleontological Conference is being held in Cincinnati, OH and they have arranged for a field trip to the Creation Museum! So if you are in the area the morning of Wednesday, June 24th, and you want to "become better aware of how their (paleontologists) work and roles in society are portrayed by creationists, themes that are conveyed vividly at the museum", then come on down!
I was excited, so I paid for my ticket when I registered for the conference. Hope to see you there!
I misread the title of this post as "Intelligent Design Snort". Now I'm thinking that would be more accurate.
Hold your horses!!!! I decided to use the way back machine and looky what I found:
I smell a cut and paste job!
#5
Yes, you can:
function faithSearch(needle, haystack) {
//Please, dear Lord, put the result of this search in the
//variable i. Please, Lord. Please please please, Lord.
return i;
}
Paleos said:
Is it me, or does this "field trip" sound a bit like paleontologists fancying taking some time out for a giggle?
Either that, or they've heard a rumour that they have free beer available somewhere in the creation museum!
Not so off topic.
In case anybody has forgotten to do the right thing,
PZ would really like to win an iPod Touch, here:
http://scienceblogs.com/pharyngula/2009/04/id_really_like_to_win_an_ipo…
Meh.
I still prefer Mergesort.
#22 GAZZA
Heathen!
In fact, on closer examination I have to say that these Intelligent Sorter dudes obviously use the same flawed naive mathematics that their ID buddies use.
The probability of a list of N items being in any given order is only 1/N! if all N are distinct. If two or more N are equal, then the probability is very different. Indeed, if all N are equal, then the probability of them being in that order is 1, regardless of N (>0). This is clearly something we might ascribe to chance.
Therefore, lists of size N have varying probability; we need to examine the list more closely before we may conclude design. :)
I really thought I was missing something here. Like I wasn't versed enough or not quite smart enough to understand it. Obviously I was wrong. It seems to be utter tripe.
#5 Tristanm
I am such a nerd... I came here to say the exact same thing.
Yes you were missing something there: satire, not tripe.
This seems to be a variation of "bogosort".
In bogosort, the list is re-arranged randomly, and then checked for being in order. Since there are n! ways to order the list (assuming no ties), this runs in O(n!) time, an incredibly bad sort. But, under the "many worlds" interpretation of quantum mechanics, there exists a world in which the list is sorted right the first time. (Hence, O(n) time, since verifying the list needs to be verified.)
I guess if the "designer" chooses to make our list perfect the first time, and we trust him to do it, then we don't even have to check it. Wow -- since god loves us, our sorts run in constant time (i.e., no time at all)!
Why didn't Donald Knuth think of that?
As long as they didn't write that algorithm in EMACS, I'm fine with it. Everyone knows that only pedophiles and murderers would use an editor like EMACS. All hail to the mighty vi!
I WUZ POED?
Tristanm is right: general-purpose sorts are O(n log n) at best. However, specialized data can be sorted faster; radix sort will sort fixed-length integers in O(kb) time, where b is the base and k is the number of columns.
I've never heard of Quicksort having trouble with very large data sets, assuming they're not already sorted. I've seen it have more trouble with very small data sets, which can be solved by stopping the recursion when the partition is smaller than a fixed number (32 seems to be a popular number of elements), and then using insertion sort to finish the job (since the Quicksort moved most of the elements close to where they belong, the insertion sort runs in approximately O(n)).
That's all well and good, but it has to be made much more complicated. See, we know that it's all true, yet complicated math makes it into science.
So FAIL. We can't sell books with that, and we can't try to claim that nazi scientists have suppressed anything that simple. Behe is sciency. Dembski is sciency. This is the absolute truth, the trouble being that it isn't sciency. To be taught in schools, and to make money, it must be sciency.
Glen D
http://tinyurl.com/6mb592
There is only one true sort! All others are blasphemy!
(Never mind that the true sort is illogical, inefficient and doesn't reflect reality...)
Presumably, also, if you do check your list to see if it's already sorted (which makes you a Doubting Thomas, aka a skeptic), and you find out that it isn't, it just proves you didn't pray hard enough.
This algorithm was clearly invented by cdesign sortistists.
If you're into silly CS things, David Morgan-Mar (the author of the above sorting algorithm) has a bunch more on his site. And yea, he's definitely not a creationist/ID person.
David Morgan-Mar is an atheist who writes a wonderful webcomic: http://irregularwebcomic.net/
For a great explanation of his world-view see: http://irregularwebcomic.net/1609.html
Finally! Say goodbye to quicksort! Merge sort, hit the road! We've got an O(1) sort! In fact, this is just the beginning: I bet we can apply this in other areas, too. Prime factorization in O(1), here we come!
Good going. Now, all we need is an Intelligent Design search, a something to generate the Knowledge of Good and Evil Tree, the Eternal Life Tree (I assume this will turn out to be infinite recursion) and then computer science will be done.
Why not try for a truly prestigious journal, like Progress in Complexity, Information and Design? Oh, or did that die due to a lack of ID science?
Glen D
http://tinyurl.com/6mb592
//Please, dear Lord, put the result of this search in the
//variable i. Please, Lord. Please please please, Lord.
return i;
I actually laughed out loud at that :-)
I remember a "creationist algorithm" article in JIR (Journal of Irreproducible Results). It was presented as a counterpart to the standard Genetic Algorithm for global function minimisation.
In a rather unsubtle parody of creationist arguments, the algorithm basically assumed you already had the desired answer.
Can't find the reference now, and JIR doesn't appear to be web searchable.
No. Really. It's perfect. Don't touch it. Can't you see? It had to be like that in order for us to be able to say it had to be like that. That's the order and it's implicit in the order because it couldn't be otherwise without intent. So don't touch it. The sort has already been done.
Anybody got an aspirin? I feel out of sorts.
Who cares what O() is? Just let the algorithm run and then send the result back in time to now. Of course then you'd be tempted to cut the power to save energy...
P.S. GAZZA wins the thread. Geiger looses points for being too literal.
New Scientist* had a piece a while back on theoretical work (which someone had actually done for there job) on algorithms for a computer that could send data back in time. The basically went "First check if the answer is already waiting for you. If not do the calculation by brute force and send it back in time to when you looked." Now with naive assumptions this means the answer will always be there waiting for you, but what if the universe ends before the calculation (O NOES!)?
They proved there was a work around based on recursively breaking up the problem that would guarantee that the answer was just there waiting. It was pretty damn cool.
I know, I know; we aren't talking to NS atm, but this was good stuff.
How embarrassing. I didn't spot that this was DMM's site.
Seconding the recommendation of Irregular Webcomic.
The good Reverend won't like it, though.
I'm probably talking out of my arse since I don't know much about algorithms, but what about Spaghetti sort?
Well, you haven't defined your variables, so I'm going to have to make some assumptions.
4=chari
Since the left hand side is all real, then (assuming the variables are real):
char=0
Now, I'm going to assume that c is the speed of light in vacuo, and h is Planck's constant. Therefore:
ar=0
I don't know any constants labelled a or r, thus:
If a=0, then r can take any real value.
Similarly, if r=0, then a can take any real value.
Sorry, I'm a nerd, and I'm bored.
OH CRAP!
I just assumed 4=0.
I'm a nerd, I'm bored, and I'm obviously very tired.
@#19:
"function faithSearch(needle, haystack) {
//Please, dear Lord, put the result of this search in the
//variable i. Please, Lord. Please please please, Lord.
return i;
}"
Psh. As if God would use Javascript.
Massive static electrical discharge followed by tremendous rolling booming sound. End user fried to a crisp collapses in little pile of ash... "Please refine search criteria"
I laughed out load at this one. Until I realized this is actually the creationist "argument".
You can't satirize fundamentalists.
@#19:
"function faithSearch(needle, haystack) {
//Please, dear Lord, put the result of this search in the
//variable i. Please, Lord. Please please please, Lord.
return i;
}"
Psh. As if God would use Javascript.
Of course God would use Javascript. The Universe is Lisp-based after all.
I wonder if my old CS prof that did not believe in evolution nor evolutionary algorithms will be attempting to teach this in the near future...
@52
everyone knows god would use lisp, maybe perl, or if was feeling bored ...
"function faithSearch(needle, haystack) {
//Please, dear Lord, put the result of this search in the
//variable i. Please, Lord. Please please please, Lord.
return i;
}"
Syntax error. You missed off the Amen...
toth is right. Everyone knows that god writes in Python.
http://xkcd.com/353/
http://xkcd.com/413/
I think I might even be able to code an implementation of this:
int idSort (const int deck[], bool deckIsSorted)
{
#define PROGRAMMER_HAS_PRAYED deckIsSorted
if (!PROGRAMMER_HAS_PRAYED) {
// The programmer didn't pray hard enough!
return idSort(deck, PROGRAMMER_HAS_PRAYED);
} else {
// God put the deck in order for us.
return 0;
}
It even solves the constant-time issues! And it's useful, too!
(Stack overflows are just a sign that you aren't Christian enough for God to listen to you - the implementation isn't wrong!)
Kill them all, and let god the designer sort them out!
toth @ 49
God uses Javascripture
par rum pump
/groan
#45
Stephen Baxter used this idea in a novel, it was a pretty interesting read but I can't recall the name. It is one of the novels occurring late in the Xelee sequence.
Sorry, fellas, but everyone knows that God wrote in Lisp code.
MP3 available here. Or just Google it.
This particular article reminds me of one of my Computer Science classes, taught by the then head of that department. It was called Cro-Magnon sort.
Basically, you take the items, randomize them, and check them. If they are in sorted order, you're good. If not, repeat the process. This sort has the amazing quality of potentially being able to sort ANY list EVER with a single iteration!
Or course it also has the potential of approaching infinity in time, but who cares about the bad stuff, eh?
I think this is the dumbest post I have read on this blog.
Almost, but not quite. http://xkcd.com/224/
I think this is the dumbest post I have read on this blog.
...and Randy's stock and trade is posting professional-grade stupid, so he should know.
Yeah, it is possible to get near O(n) with insertion sort if the data is already nearly sorted. Still, if it's not nearly sorted, it's O(n^2). The really nice algorithms that get O(n*log(n)) tend to fall apart with small data sets horribly. And Quick Sort dies at super large data sets due to recursing to death.
You have just enough knowledge to get everything wrong. As uzi noted, some data sets can be sorted in O(n) -- not using insertion sort; sequentially numbered items can be sorted simply by dropping them into the properly numbered slot. "really nice" O(nlogn) algorithms do not "fall apart horribly" with small data sets, they simply don't do as well as simpler sorts like insertion sort. The obvious solution is to use a simpler sort when the subset size is small. And quicksort does not recurse to death with super large data sets if you simply sort the smaller subset first -- that limits the stack depth to logn. BTW, quicksort is on average O(nlogn), but it has O(n2) worst cases.
The C++ library uses introsort, which is quicksort until the stack depth reaches a calculated threshhold and then switches to heapsort. It is extremely efficient and not only doesn't "fall apart" or "die" on either large or small data sets, but unlike quicksort it has O(nlogn) worst case behavior.
Or course it also has the potential of approaching infinity in time
The technical term for that is "never finishing".
I think this is the dumbest post I have read on this blog.
Exactly.
I'm probably talking out of my arse since I don't know much about algorithms, but what about Spaghetti sort?
Good for robots, not digital computers.
I've never heard of Quicksort having trouble with very large data sets, assuming they're not already sorted.
Being already sorted isn't a problem when using median-of-3 to choose the pivot point, which virtually all practical quicksort algorithms do.
I've seen it have more trouble with very small data sets, which can be solved by stopping the recursion when the partition is smaller than a fixed number (32 seems to be a popular number of elements)
The optimal number depends on the machine architecture, but 32 is generally too large.
and then using insertion sort to finish the job (since the Quicksort moved most of the elements close to where they belong, the insertion sort runs in approximately O(n)).
This is somewhat confused. There are two ways to use insertion sort with quicksort. One is to switch to insertion sort when the partition size is small; each such partition is unsorted, so the time to sort a partition is O(p2) and the total insertion sort time is O(p2n/p) = O(np). The other way is to simply not sort small partitions, and then run a single insertion sort over the whole array at the end; the elements are indeed "near where they belong" because the unsorted partitions have been sorted relative to each other, but they are unsorted, so the time is again O(np).
In bogosort, the list is re-arranged randomly, and then checked for being in order. Since there are n! ways to order the list (assuming no ties), this runs in O(n!) time,
Uh, no; there's no guarantee that the random orderings are unique. Average performance is O(n * n!) and worst case is infinite.
But, under the "many worlds" interpretation of quantum mechanics, there exists a world in which the list is sorted right the first time. (Hence, O(n) time, since verifying the list needs to be verified.)
As Wikipedia says: "Note, however, that even here there is no free lunch – while this algorithm is O(n) in time, permuting the list requires that we consume O(n log n) bits of quantum randomness. (It also assumes that destroying the universe is O(1) in operation - since it has to be executed at most n-1 times.)"
I really thought I was missing something here. Like I wasn't versed enough or not quite smart enough to understand it. Obviously I was wrong. It seems to be utter tripe.
No, you were right.
In fact, on closer examination I have to say that these Intelligent Sorter dudes obviously use the same flawed naive mathematics that their ID buddies use.
Yes, but ...
The probability of a list of N items being in any given order is only 1/N!
Ahem. The claim is that "The probability of the original input list being in the exact order it's in is 1/(n!)." In fact, the probability of that is 1, which is not so unlikely that it would be absurd to say it happened by chance.
"The probability of the original input list being in the exact order it's in is..." 1. Every "original input list" is in the exact order it's in.
If you make a mistake with the original assumption, all the rest of your work must be thrown out.
What a straw man of ID.
It is not just that it has a low probability, but that it has a low probability under naturalism and a high probability under intelligent design. (Learn Bayes' theorem folks).
It is not just low robability, its specified probability.
You cannot refute the CSI (complex specified information). The law of conservation of CSI says that it cannot be increased without intelligence
The law of conservation of CSI says that it cannot be increased without intelligence
Actually, if you actually look at Dembski's bafflegab about CSI, he appears to prove that nothing can increase CSI via a search function, neither random search or search with "intelligence." (Scare-quotes for question-begging stupidity of IDers use of term.)
But it's moot; CSI is a bogus concept, entirely made up to sound sciency, with no basis in reality and less applicability to biological systems.
But, please, do go on pretending to be smart and to understand Bayesian probability. It's quite entertaining so far.
We are not amused.
Pretty good, but what about ThunderSort?
http://www.turkishthunder.com/thundersort.html
What a straw man of ID.
It is not just that it has a low probability, but that it has a low probability under naturalism and a high probability under intelligent design. (Learn Bayes' theorem folks).
We know it, and we know that you're talking rubbish. We have "It's the way it is because of contingent evolution" vs. "It's the way it is because it was designed that way". To claim that the latter has a high conditional probability is to beg the question, incredibly stupidly, just as the Algorithm Description does and just as all IDiots do.
You cannot refute the CSI (complex specified information). The law of conservation of CSI says that it cannot be increased without intelligence
If it says that, then it is self-refuting, because it implies a divergence of increasingly complex intelligences. The fact is that Dembski's nonsense has been thoroughly refuted by Wesley Elsberry, Mark Perakh, and others.
GAZZA at #24 commented:-
So, if all N are the same, there is no cause to invoke a Designer.
Thus, if all men are created equal, then they have no need of a god at all.
Therefore ID is unconstitutional...