Illustrated Sorting Algorithms

http://sorting.at

by thesprawl • 12 years ago

142 37 12 years ago

sorting.at

c16• 12 years ago

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

As already said, this is very nicely done.

jonas21• 12 years ago

I'll just leave this here:

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

lolo_• 12 years ago

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/

Artemis2• 12 years ago

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.

TheLoneWolfling4• 12 years ago

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.

robertnn• 12 years ago

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

TheLoneWolfling4• 12 years ago

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.

TwoBit3• 12 years ago

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.

TheLoneWolfling4• 12 years ago

At which case: why bother using quicksort?

jader201• 12 years ago

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.

gavinpc• 12 years ago

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.

krapp• 12 years ago

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.

TwoBit3• 12 years ago

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.

dspillett• 12 years ago

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.

LarryMade2• 12 years ago

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

wodenokoto• 12 years ago

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.

dfc2• 12 years ago

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.

nubs• 12 years ago

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

dfc2• 12 years ago

You are wonderful.

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

Edmond• 12 years ago

crash my browser.

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

http://schoolnotez.com/

csch• 12 years ago

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

mmanfrin• 12 years ago

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

tight_scientist• 12 years ago

Completely agree. It's what I always use.

josso• 12 years ago

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

jurassic• 12 years ago

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

TwoBit3• 12 years ago

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

cvbncvbncgbc• 12 years ago

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.

surfnerd• 12 years ago

Naicee visualization. What does it use ?

bhauer• 12 years ago

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

xpda• 12 years ago

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

clintonc• 12 years ago

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 :)

jlebar• 12 years ago

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

danielstocks• 12 years ago

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

Illustrated Sorting Algorithms

Related Stories