Illustrated Sorting Algorithms | Hacker News Reader

Illustrated Sorting Algorithms

sorting.at

142 pointsthesprawl37 comments

No idea what this is. It keeps crashing Firefox for me. And unfortunately, restarting Firefox only restores the same window, sending me into a loop of crashing.

I have no idea if it's FireFox's fault that it crashes, but you'd hope the developer would test on the major browsers.

> I have no idea if it's FireFox's fault that it crashes,

It almost certainly is. It could be an OS or graphics driver problem, but these options are far less likely.

It certainly isn't the site's problem: in the ideal world we don't live in (where browsers, drives and OSs have no faults) it is not be possible for any browser hosted code to take down the whole browser or worse, even if deliberatey trying to do so. The site may be doing something that highlights a problem elsewhere, that the site's designer may be able to work around, but that problem is not their fault.

If the crash is repeatable it would be useful to report it to the Firefox team as that may help them find the bug and therefor either fix it or report it further upstream if it isn't in their code.

> but you'd hope the developer would test on the major browsers.

The developer probably did, if by "major browsers" you mean "the latest of the two of the big three that are available cross platform, and maybe a mobile browser or two" as they were at the time of the site/app's last major update. But testing on all common browsers can be a time consuming process that demands significant resources (a Windows instance for each IE version considered, a Windows, Linux, and OSX instance for each version of Firefox or Chrome considered (as they sometimes hit different problems on different platforms), oh and don't forget that there are several common Linux arragements that you'll see actively used by many people, 8 Windows variants (excluding service packs as variants, 7 if you exclude XP), and a few OSX ones, and that is before you consider 32-bit and 64-bit variations and I've not even touched mobile platforms yet, ..., ..., ...).

Multi-browser testing can be a painful process and even if you either stick to a limited number of combinations (that covers for example 80% of your audience) and/or have the testing automated by some means, the results of tests that you run now might not be relevant tomorrow after a browser maker releases an update or an OS maker releases an update that somehow triggers a latent bug in a browser.

tl;dr: if the browser crashes that is never the site/app's developer's fault. If the site/app fails to work correctly in a given (recent and relatively standards compliant) browser than it probably is but there are practical limitations on what we can do to try acheive 100% correctness.

Are you sure you have updated Firefox? My firefox ALWAYS asks me if I want to restore the previous session. It also allows me to choose which tabs/windows I want to restore.

It also doesn't crash on this page either.

I was interested to notice that Firefox (28) re-opened all of the pages except that one.

But do open it in Chrome, it's lovely.

It crashed Firefox for me almost immediately.

I would have thought we'd gotten past the need for browser-specific code and the days of having to decide between ignoring the Netscape people or ignoring the IE people. It's bad enough that sites which simply don't work in a certain browser are becoming more commonplace again, now apparently some code is essentially hostile in the wrong browser.

Crashed on Firefox for me too, saw two - the diagrams looked pretty.

Thread Hijack: A little while ago there was a link on HN to a visual explanation of text compression, but I do not remember the compression format. It was the first time I ever understood how text compression works. There was a paragraph of text and the author stepped through the compression of the paragraph with an accompanying depiction of the original paragraph. Does this sound familiar to anyone? It was the first time I ever really understood text compression and I have been looking for it ever since. It was just text, no D3 and no flash, just plain old ascii.

http://jvns.ca/blog/2013/10/24/day-16-gzip-plus-poetry-equal...

You are wonderful.

The good stuff is here: http://www.infinitepartitions.com/art001.html

Very well done. I like the step-by-step animation.

Another nice sort visualization is Sortviz.org. For example:

http://sortvis.org/algorithms/combsort.html

and

http://sortvis.org/algorithms/heapsort.html

I'll just leave this here:

https://www.youtube.com/watch?v=ywWBy6J5gz8

I'm really partial to this site for visualizing: http://www.cs.usfca.edu/~galles/visualization/Algorithms.htm...

Completely agree. It's what I always use.

Very nice indeed.

I did a basic hack on a sorting visualisation a while ago [0] and have felt for a long time there is a lot more possible with algorithm visualisation in general than has been done in the past. Hopefully we see lots more awesome stuff like this in the future :)

[0]:http://ljs.io/projects/rainbow/

Too bad it's missing Timsort, which is the fastest stable sort and the standard for some standard libraries.

Calling it fastest is not fair. Timsort appears to be very fast because most real world data we operate it on is somewhat sorted, but requires O(n) extra memory. It simply depends on the situation and data.

I wish it had a "pathological case" option for data to sort per-algorithm.

In particular: Quicksort, which (unless you're willing to make an (expensive) call to a (P)RNG per iteration) has a worst case of O(n^(2)) time.

Despite that no real-world quicksort implementations have that worst case (due to fallbacks to other sorts), it seems like it's useful to see the pathological case of pure quicksort anyway.

At which case: why bother using quicksort?

Because in the real world, where all our code must actually run, quicksort beats practically every other algorithm on the vast majority of inputs. Its cache behavior is better than heap sort, its memory usage is lower than merge sort, and even its O(log n) memory usage is efficiently allocated on the stack as opposed to hitting a slow system allocator.

"Engineering a Sort Function"[0] covers this quite well.

In some experiments of my own, I've found that even Smoothsort[1] (an algorithm specifically designed to have a smooth transition from linear to linearithmic behavior on nearly-sorted input) can't beat the C++ system's introsort (a quicksort variation with a fallback to heapsort) in already-sorted inputs.

[0] http://www.skidmore.edu/~meckmann/2009Spring/cs206/papers/sp...

[1] http://www.keithschwarz.com/smoothsort/

It's simple(relatively) and almost always quite fast. Or would you rather use slowsort?

Quicksort is not simple if you have to build in an entire other sorting algorithm as a failsafe.

And merge sort is often faster, especially if the comparison function is relatively expensive.

Yes, sometimes, but it also uses more memory. In practice, with real problems, quicksort wins with in-memory sorting, and mergesort wins with too big for memory data sets.

Why would the worst case change if you use a random number for choosing the pivot?

Ah.

Technically, the worst case stays the same.

In actuality, the worst case occurring via random chance is not a problem, as it occurs vanishingly infrequently. The problem is malicious input.

Just finished writing revision notes on sorting algos and I come across this. Damn it!

As already said, this is very nicely done.

It's tough to be Sorting out Sorting, although I grant that it doesn't have all the newfangled algorithms that this page has.

Really, you need to watch this if you haven't. https://www.youtube.com/watch?v=SJwEwA5gOkM

Fascinating!

Another sorting visualization that I like is this one: https://www.youtube.com/watch?v=kPRA0W1kECg. It is well-known but the way everything falls back into place at each time... that's very satisfying.

Points deducted for incorrect O's. Quick Sort is not O(n log n), and merge sort is not O(n^2)

Well, Quick Sort is O(n log n) on average, but you know that. Also, anything that's O(n log n) is also O(n^2), which means that the author is the worst kind of correct -- but you knew that too :)

I always find this one nice to watch: 15 sorting algorithms in 6 minutes (with sound) https://www.youtube.com/watch?v=kPRA0W1kECg

Very pretty indeed! I did a similar thing in JavaScript but inspired by the "sound of sorting" http://webcloud.se/Assortment/

crash my browser.

here's another sorting algo sim: click the computer science example.

http://schoolnotez.com/

Yep, it can be nice to have algorithms visualized. I'm also fond of http://www.sorting-algorithms.com/

Really nice work. It runs fine on my browser (Chrome 34 on Mavericks.)

Naicee visualization. What does it use ?

Reply on news.ycombinator.com