6 ms·

Sorting - We're Doing It Wrong

66 points by cheeaun 14y ago

TamDenholm 14y ago
This is a very cool visualiser that was posted on HN before if anyone feels like playing: http://visualsort.appspot.com/ http://visualsort.appspot.com/
- y0ghur7_xxx 14y ago
  previous discussion: http://news.ycombinator.org/item?id=3040157 http://news.ycombinator.org/item?id=3040157
lliiffee 14y ago
Wow-- apparently Mergesort can be implemented in-place!?
- Scaevolus 14y ago
  Yes, but people usually don't since it requires more swap operations and is pretty hard to get correct.
  - its_so_on 14y ago
    what, "hard to get correct"? Are we talking about fundamental computer science that literally consists of implementing an algorithm made out of compare and swap/move elements...? I can't imagine any sort algorithm for which it can possibly be legitimate to say it's 'hard to get correct' unless it's in the sentence 'it's hard for a first-year computer science student to get correct.' i mean, what is more traditional and basic than implementing tricky sort algorithms?
    - bazzargh 14y ago
      How about binary search? "When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it,[7] and another study shows that accurate code for it is only found in five out of twenty textbooks.[8] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.[9]" http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues http://en.wikipedia.org/wiki/Binary_search_algorithm#Impleme...
      - morsch 14y ago
        I just learned that Java has an unsigned right shift operator >>> from an article cited as a reference in that Wikipedia section. The article has some more details on the subtleties of binary search. For instance, the 20 year old bug in an algorithm proven to be correct was down to integer ranges: int mid = (low + high)/2; breaks (obviously in retrospect, am I missing something?) for low + high > Integer.MAX_INTEGER It can be replaced by the elegant (but to me, somewhat oblique) int mid = (low + high) >>> 1; http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.de/2006/06/extra-extra-read-a... Also from that page, here's the link to the bug in Sun's tracker, priority 2-High, evaluation: "Can't even compute average of two ints" is pretty embarrassing. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582
- pestaa 14y ago
  I had this feeling when we implemented it in school, but couldn't think it through. My teacher told me it is not possible and convinced me to give up.
- brianhempel 14y ago
  The video is not demonstrating an in-place merge sort. Notice how the sorted pairs suddenly merge. There's another buffer (not included in the visualization) where each merged list is temporarily stored while it is being built up. The sudden merger is when that temporary buffer is copied back into the main list.
gooderlooking 14y ago
Maybe I'm the only one who missed the memo, but in case anyone else is wondering what a hash is doing in JS: "When writing (in text, not in JavaScript) about properties on specific prototypes, you may use the JavaScript notation, foo.prototype.bar. However, this shorter (non-JavaScript) notation is often used instead: foo#bar. Basically, the hash (#) stands for .prototype. — fancy huh?" http://mathiasbynens.be/notes/javascript-prototype-notation http://mathiasbynens.be/notes/javascript-prototype-notation
- wahnfrieden 14y ago
  A bit confusing since it's a common convention to use # to refer to instance members, e.g. Foo#bar means my_instantiation_of_foo.bar
  - tantalor 14y ago
    That's exactly what happens in the JavaScript case: new Array().sort === Array.prototype.sort # true
- geuis 14y ago
  You're not alone. I've never seen this before either. Look, when you're writing an article about programming, stick to spelling things out properly. It's ok to use acronyms when talking about companies (AT&T, IBM), nations (USA, USSR), or long technical terms as long as you define them early in the document so the reader knows what to expect. Programming docs should explicitly refer to code in the language being discussed. Array.prototype.sort tells me exactly what you're talking about and my brain doesn't have to make mental leaps to understand what is being said. If its a language I'm not familiar with, like Objective C for example, then I probably will want to copy and search on code being demoed to learn about it. This would be very hard to do if I have to translate your custom abbreviations into the terminology everyone else in the world uses. Keep it simple and succinct.
- crazygringo 14y ago
  This was confusing for me as well. Why on earth would anyone create a separate "text" notation for a programming language? Please just stick to writing out ".prototype", if writing for a general audience.
tantalor 14y ago
This is fixed in Python: The sort() method takes optional arguments for controlling the comparisons. "key" specifies a function of one argument that is used to extract a comparison key from each list element. In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function. This is because cmp is called multiple times for each list element while key and reverse touch each element only once. http://docs.python.org/library/stdtypes.html http://docs.python.org/library/stdtypes.html
numeromancer 14y ago
This is worth reading for that video alone. Mergesort was particularly cool.
Rickasaurus 14y ago
Another great example of Javascript being awful.
- tomjakubowski 14y ago
  Care to elaborate?
Camillo 14y ago
For a moment, I thought there was actually something new about sorting. That turned out not to be the case, of course. I understand the importance of linkbait titles, but specifying the context (e.g. "we're doing it wrong in JavaScript") would save people time without weakening the impact on those who might be interested in the article (JavaScript developers).
- cldrope 14y ago
  Thank you. HN seems to be subject to tons of vague or mildly misleading titles and I'm getting pretty sick of it. I wouldn't be bothered as much, but in some places if you get into too many technical details it seems to confound people and then frustrate them. This is kind of silly since I'm still in college and probably one of the least educated coders here. Seems wrong to be then downvoted for using basic technical knowledge in a place called Hacker News.
ruxkor 14y ago
javascript sorting: having expected a sorting somewhat similar to python and being very... surprised that javascript essentially sorts everything but primitive types by comparing their String counterparts, I decided to implement a more sensible compare function, similar to e.g. python: https://gist.github.com/2772234 https://gist.github.com/2772234 I am currently using this in server only environments, so there is no comparison for DOM elements.

66 points by cheeaun 14y ago

This is a very cool visualiser that was posted on HN before if anyone feels like playing: http://visualsort.appspot.com/ http://visualsort.appspot.com/

y0ghur7_xxx 14y ago
previous discussion: http://news.ycombinator.org/item?id=3040157 http://news.ycombinator.org/item?id=3040157

lliiffee 14y ago

Wow-- apparently Mergesort can be implemented in-place!?

Scaevolus 14y ago
Yes, but people usually don't since it requires more swap operations and is pretty hard to get correct.
- its_so_on 14y ago
  what, "hard to get correct"? Are we talking about fundamental computer science that literally consists of implementing an algorithm made out of compare and swap/move elements...? I can't imagine any sort algorithm for which it can possibly be legitimate to say it's 'hard to get correct' unless it's in the sentence 'it's hard for a first-year computer science student to get correct.' i mean, what is more traditional and basic than implementing tricky sort algorithms?
  - bazzargh 14y ago
    How about binary search? "When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it,[7] and another study shows that accurate code for it is only found in five out of twenty textbooks.[8] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.[9]" http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues http://en.wikipedia.org/wiki/Binary_search_algorithm#Impleme...
    - morsch 14y ago
      I just learned that Java has an unsigned right shift operator >>> from an article cited as a reference in that Wikipedia section. The article has some more details on the subtleties of binary search. For instance, the 20 year old bug in an algorithm proven to be correct was down to integer ranges: int mid = (low + high)/2; breaks (obviously in retrospect, am I missing something?) for low + high > Integer.MAX_INTEGER It can be replaced by the elegant (but to me, somewhat oblique) int mid = (low + high) >>> 1; http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.de/2006/06/extra-extra-read-a... Also from that page, here's the link to the bug in Sun's tracker, priority 2-High, evaluation: "Can't even compute average of two ints" is pretty embarrassing. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582
pestaa 14y ago
I had this feeling when we implemented it in school, but couldn't think it through. My teacher told me it is not possible and convinced me to give up.
brianhempel 14y ago
The video is not demonstrating an in-place merge sort. Notice how the sorted pairs suddenly merge. There's another buffer (not included in the visualization) where each merged list is temporarily stored while it is being built up. The sudden merger is when that temporary buffer is copied back into the main list.

gooderlooking 14y ago

Maybe I'm the only one who missed the memo, but in case anyone else is wondering what a hash is doing in JS: "When writing (in text, not in JavaScript) about properties on specific prototypes, you may use the JavaScript notation, foo.prototype.bar. However, this shorter (non-JavaScript) notation is often used instead: foo#bar. Basically, the hash (#) stands for .prototype. — fancy huh?" http://mathiasbynens.be/notes/javascript-prototype-notation http://mathiasbynens.be/notes/javascript-prototype-notation

wahnfrieden 14y ago
A bit confusing since it's a common convention to use # to refer to instance members, e.g. Foo#bar means my_instantiation_of_foo.bar
- tantalor 14y ago
  That's exactly what happens in the JavaScript case: new Array().sort === Array.prototype.sort # true
geuis 14y ago
You're not alone. I've never seen this before either. Look, when you're writing an article about programming, stick to spelling things out properly. It's ok to use acronyms when talking about companies (AT&T, IBM), nations (USA, USSR), or long technical terms as long as you define them early in the document so the reader knows what to expect. Programming docs should explicitly refer to code in the language being discussed. Array.prototype.sort tells me exactly what you're talking about and my brain doesn't have to make mental leaps to understand what is being said. If its a language I'm not familiar with, like Objective C for example, then I probably will want to copy and search on code being demoed to learn about it. This would be very hard to do if I have to translate your custom abbreviations into the terminology everyone else in the world uses. Keep it simple and succinct.
crazygringo 14y ago
This was confusing for me as well. Why on earth would anyone create a separate "text" notation for a programming language? Please just stick to writing out ".prototype", if writing for a general audience.

tantalor 14y ago

This is fixed in Python: The sort() method takes optional arguments for controlling the comparisons. "key" specifies a function of one argument that is used to extract a comparison key from each list element. In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function. This is because cmp is called multiple times for each list element while key and reverse touch each element only once. http://docs.python.org/library/stdtypes.html http://docs.python.org/library/stdtypes.html

numeromancer 14y ago

This is worth reading for that video alone. Mergesort was particularly cool.

Rickasaurus 14y ago

Another great example of Javascript being awful.

tomjakubowski 14y ago
Care to elaborate?

Camillo 14y ago

For a moment, I thought there was actually something new about sorting. That turned out not to be the case, of course. I understand the importance of linkbait titles, but specifying the context (e.g. "we're doing it wrong in JavaScript") would save people time without weakening the impact on those who might be interested in the article (JavaScript developers).

cldrope 14y ago
Thank you. HN seems to be subject to tons of vague or mildly misleading titles and I'm getting pretty sick of it. I wouldn't be bothered as much, but in some places if you get into too many technical details it seems to confound people and then frustrate them. This is kind of silly since I'm still in college and probably one of the least educated coders here. Seems wrong to be then downvoted for using basic technical knowledge in a place called Hacker News.

ruxkor 14y ago

javascript sorting: having expected a sorting somewhat similar to python and being very... surprised that javascript essentially sorts everything but primitive types by comparing their String counterparts, I decided to implement a more sensible compare function, similar to e.g. python: https://gist.github.com/2772234 https://gist.github.com/2772234 I am currently using this in server only environments, so there is no comparison for DOM elements.