4 ms·

Inefficient sort algorithms (2001)

37 points by samaysharma 11y ago

ericfrederich 11y ago
This is my favorite one: https://news.ycombinator.com/item?id=8798202 http://dis.4chan.org/read/prog/1295544154/
smhenderson 11y ago
After reading the good news about MS and OpenSSH this was the best quote from the article for me: The identity of the serpent is obscure. It is rumored that he is currently running a computer company in Redmond. People get pretty riled up about sorting!
chowells 11y ago
Always funny to see your own name come up in submissions to a story from 14 years ago..
twic 11y ago
Thanks to the Web, we can now do so much worse: http://gkoberger.github.io/stacksort/ http://gkoberger.github.io/stacksort/ So much worse: http://jort.technology/ http://jort.technology/
FeepingCreature 11y ago
See also this classic of a paper: Pessimal Algorithms and Simplexity Analysis (pdf) http://www.researchgate.net/profile/Andrei_Broder/publication/2805500_Pessimal_Algorithms_and_Simplexity_Analysis/links/00b7d5187d62f61ee4000000.pdf http://www.researchgate.net/profile/Andrei_Broder/publicatio... > Table search can be viewed as a special cast of the following more general problem. We are given a “maze”, i.e. an undirected graph G with n nodes, and an “entry” node u in it. Our task is to find a path from u to a specified “exit” node v, by walking on the maze one edge at a time. [...] > However, suppose the maze is actually quite agreeable, so much so that we wouldn’t mind spending a few extra cycles in the search for v; in fact we vaguely hope, nay, decidedly wish, that the search will take as long as possible, and even though our sense of duty prevents us from giving up the search altogether, we are not that insensitive to the primeval necessities of our human nature, and besides what is wrong with taking a more relaxed attitude to the problem, as long as we do what we are supposed to do, since we have always been told that haste makes waste, and no one needs to be perfect anyway, and so forth. With these assumptions, the problem falls squarely within the domain of our theory.
nosuchthing 11y ago
15 Sort Algorithms: Visualized & Audible https://www.youtube.com/watch?v=kPRA0W1kECg https://www.youtube.com/watch?v=kPRA0W1kECg
imh 11y ago
http://stackoverflow.com/questions/2609857/are-there-any-worse-sorting-algorithms-than-bogosort-a-k-a-monkey-sort http://stackoverflow.com/questions/2609857/are-there-any-wor...
- yellowapple 11y ago
  The Jingle Sort is the best.
bquinlan 11y ago
I actually agree with this remark: "In the talk.origins newsgroup someone made an offhand remark that they didn't see how anybody, no matter how klutzy their programming, could write an O(n^3) sort." The examples were all constructed by smart people who are deliberately trying to invent slow algorithms. I don't think that a klutzy programmer would stumble upon any of them by chance. The slowest sorting algorithm that I've seen in production was something like this: def sort(l): s = [] while len(l) > 0: m = max(l) s.append(m) l.remove(m) s.reverse() return s I looked like a hero when I reduced the main page load time for our biggest customer by 90% in one afternoon :-)
xyproto 11y ago
I can't believe sleep sort isn't there!

37 points by samaysharma 11y ago

This is my favorite one: https://news.ycombinator.com/item?id=8798202 http://dis.4chan.org/read/prog/1295544154/

After reading the good news about MS and OpenSSH this was the best quote from the article for me: The identity of the serpent is obscure. It is rumored that he is currently running a computer company in Redmond. People get pretty riled up about sorting!

chowells 11y ago

Always funny to see your own name come up in submissions to a story from 14 years ago..

twic 11y ago

Thanks to the Web, we can now do so much worse: http://gkoberger.github.io/stacksort/ http://gkoberger.github.io/stacksort/ So much worse: http://jort.technology/ http://jort.technology/

FeepingCreature 11y ago

See also this classic of a paper: Pessimal Algorithms and Simplexity Analysis (pdf) http://www.researchgate.net/profile/Andrei_Broder/publication/2805500_Pessimal_Algorithms_and_Simplexity_Analysis/links/00b7d5187d62f61ee4000000.pdf http://www.researchgate.net/profile/Andrei_Broder/publicatio... > Table search can be viewed as a special cast of the following more general problem. We are given a “maze”, i.e. an undirected graph G with n nodes, and an “entry” node u in it. Our task is to find a path from u to a specified “exit” node v, by walking on the maze one edge at a time. [...] > However, suppose the maze is actually quite agreeable, so much so that we wouldn’t mind spending a few extra cycles in the search for v; in fact we vaguely hope, nay, decidedly wish, that the search will take as long as possible, and even though our sense of duty prevents us from giving up the search altogether, we are not that insensitive to the primeval necessities of our human nature, and besides what is wrong with taking a more relaxed attitude to the problem, as long as we do what we are supposed to do, since we have always been told that haste makes waste, and no one needs to be perfect anyway, and so forth. With these assumptions, the problem falls squarely within the domain of our theory.

nosuchthing 11y ago

15 Sort Algorithms: Visualized & Audible https://www.youtube.com/watch?v=kPRA0W1kECg https://www.youtube.com/watch?v=kPRA0W1kECg

imh 11y ago

http://stackoverflow.com/questions/2609857/are-there-any-worse-sorting-algorithms-than-bogosort-a-k-a-monkey-sort http://stackoverflow.com/questions/2609857/are-there-any-wor...

yellowapple 11y ago
The Jingle Sort is the best.

bquinlan 11y ago

I actually agree with this remark: "In the talk.origins newsgroup someone made an offhand remark that they didn't see how anybody, no matter how klutzy their programming, could write an O(n^3) sort." The examples were all constructed by smart people who are deliberately trying to invent slow algorithms. I don't think that a klutzy programmer would stumble upon any of them by chance. The slowest sorting algorithm that I've seen in production was something like this: def sort(l): s = [] while len(l) > 0: m = max(l) s.append(m) l.remove(m) s.reverse() return s I looked like a hero when I reduced the main page load time for our biggest customer by 90% in one afternoon :-)

xyproto 11y ago

I can't believe sleep sort isn't there!