Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Sorting Algorithms — Boring Until You Add Sound

Soulskill posted more than 3 years ago | from the bloop-bleep-bloop dept.

Programming 118

An anonymous reader writes "Anyone who's ever taken a programming course or tried to learn how to code out of a book will have come across sorting algorithms. Bubble, heap, merge — there's a long list of methods for sorting data. The subject matter is fairly dry. Thankfully, someone has found a way to not only make sorting more interesting, but easier to remember and understand, too."

cancel ×

118 comments

Everything is better with sound (-1, Offtopic)

Anonymous Coward | more than 3 years ago | (#33315906)

Like sex, for instance.

Re:Everything is better with sound (0, Interesting)

Anonymous Coward | more than 3 years ago | (#33316110)

Ted Bundy would disagree

Easily amused (0, Flamebait)

Peach Rings (1782482) | more than 3 years ago | (#33315950)

Sorting is not a boring problem, and what are you 5 years old being amused by zoop-zap noises?

Re:Easily amused (2, Insightful)

0racle (667029) | more than 3 years ago | (#33315988)

Yes

Re:Easily amused (1)

spazdor (902907) | more than 3 years ago | (#33316864)

Bloop, ping!

Re:Easily amused (1, Funny)

Anonymous Coward | more than 3 years ago | (#33316048)

Wonderful. Just what we needed for the next generation of science fiction movies. Audible sorting!

Re:Easily amused (2, Funny)

oldspewey (1303305) | more than 3 years ago | (#33316586)

I'll create an audio interface using Visual Basic ... see if I can track an IP address.

Re:Easily amused (1)

tenco (773732) | more than 3 years ago | (#33316346)

Dunno why you're offtopic. You're right. At least about the "sorting not boring"-part :)

QuickBasic did this (3, Informative)

Bananenrepublik (49759) | more than 3 years ago | (#33315952)

Anybody who did their first programming steps with QuickBasic will remember that it came with a demo that did just this. Anyway, the videos are still fun to watch.

Re:QuickBasic did this (4, Informative)

commodore64_love (1445365) | more than 3 years ago | (#33316300)

Ditto MS BASIC 7(?) on the old 1985 Amiga - included demos with sound.

Plus TV shows, especially scifi ones, do this all the time. The computers don't have to make noise but the audio engineer added the sound to keep the show from being dull.

Re:QuickBasic did this (1)

afex (693734) | more than 3 years ago | (#33317912)

Anybody who did their first programming steps with QuickBasic

fyi, remember that the freshman in high school right now were BORN in 1996. Heck, i started my BSEE in '01 and i barely made the cutoff for playing around with quickbasic. Though i was quite fond of the gorillas demo game... : )

Sorting Out Sorting (3, Interesting)

SilverEyes (822768) | more than 3 years ago | (#33316014)

Does anyone remember "Sorting Out Sorting" (1980)? Best sorting video ever made. This is the same thing, it's good, but it was done thirty years ago. Also, "Pointy Does Pointers" (not an adult film, I swear).

Re:Sorting Out Sorting (2, Informative)

maxwell demon (590494) | more than 3 years ago | (#33316334)

Do you mean this? [youtube.com] Because as far as I can see, that one doesn't illustrate the sorting algorithm itself with sound. Disclaimer: I only watched the first three minutes.

Re:Sorting Out Sorting (3, Funny)

SilverEyes (822768) | more than 3 years ago | (#33316714)

I did watch it again after I posted my comment, I was wrong. I misremembered the video. The annoying sounds are unrelated to the algorithm.

This guy did have not-annoying sounds related to the algorithm. Also the quality is much higher.

Re:Sorting Out Sorting (2, Interesting)

MikeTheGreat (34142) | more than 3 years ago | (#33318012)

My initial reaction was "Really? Seriously?? How does this make the algorithm any more interesting, easier to understand, or easier to remember? I mean hey - I like 80's console-sounds as much as the next guy, but they're not really adding anything."

Then it hit me that (apparently) many people haven't seen the algorithms visualized like this before. As someone who's been teaching this stuff for years, I've always handed out links to visualizations like this (even if they did lack the retro-hip sound effects :) ). As a matter of fact, I think that one of the first big demonstrations of Java was an applet that demonstrated
various sorting algorithms [citation needed :) ]

Anyways, if you're interested in this sort of thing, the link I've been using is:
http://www.sorting-algorithms.com/ [sorting-algorithms.com]

I've heard good things about this place, but haven't looked through it extensively:
http://algoviz.org/ [algoviz.org]

(You know, in all the years I've been on Slashdot, I don't think I've ever wanted to create a new top-level post instead of responding to someone else's comment.... until now. Which is why I can't find the button to do so. I'd love for someone to (politely, with good humor) point out the obvious button that I'm missing)

Re:Sorting Out Sorting (1)

perlmangle (49439) | more than 3 years ago | (#33318154)

You reply to the main story, up top. Look for the box that contains "The Fine Print:" and then hit 'reply'.

Re:Sorting Out Sorting (1)

maxwell demon (590494) | more than 3 years ago | (#33318478)

Well, given the new Web 2.0 interface, it might depend on your browser (I never tried it on anything but Firefox, so I don't know), not to mention that you can select between different interfaces, but if your Slashdot interface looks remotely like mine, there should be three possibilities to reply:

The first possibility has the advantage that it's always visible (provided that your browser supports it, also you probably have to have JavaScript enabled, and it might be invisible anyway if you are looking at the story and not the comments), but it isn't exactly a button, but a link, so it doesn't exactly fir your question: In the floating box which, tells you how many comments are there, and has a fancy interface to collapse/expand the comments, which is almost as intuitive as the old dropdown menu from the pre-Web 2.0 times, but has the advantage that you can train your mouse abilities better, there's also a link "Reply", directly right of the link saying "[Number] more", and (at least for me) partially obscured by an icon which shows a small piece of paper with a pencil lying on it (it also might be a pen, at the small size it's hard to tell).

The second option has the disadvantage that you have to scroll to the correct place, below the story, but above the comments. There's a grey bar, which on the right hand side contains again two links "[Number] more" and "Reply" (again there's the pencil/paper icon, but this time it doesn't partially obscure the link). However it again doesn't fit your demand for a button.

Finally there's a third option which is the easiest to find, because unlike the two links mentioned before, it isn't very small, and which in addition fits best your demand for a button because it at least somewhat looks like a button, although looking at the page source reveals that it's again just a link. That button-link is at the very end of the page, below the comments, and to the right of another button-link which (you guessed it -- but I bet you didn't guess completely correct) contains the text "Get [Number] More Comments", and to the left of another button-link which says "Prefs" from which I conclude that whoever wrote this didn't know how to correctly spell "Preferences" (because given the large horizontal space available I cannot think of another reason to shorten it). Note, however, that this button-link lacks the paper-pencil icon. However this doesn't affect the functionality.

So in short, if you insist on a button, you're out of luck (you might, however, be able to get that by changing your preferences to another interface). However if you are content with a link that looks like a button, you can use the one on the end of the page. And if you are willing to use a link that also looks like a link, you can in addition use one of the other two links I mentioned.

OK, I hope this explanation fits your demand. If not, sorry, I've got no better humor to offer.

Re:Sorting Out Sorting (1)

EyelessFade (618151) | more than 3 years ago | (#33317222)

Obligatory watch on the first algorithm course at my local university.

Re:Sorting Out Sorting (1)

publiclurker (952615) | more than 3 years ago | (#33317500)

We always showed this in a continuous loop during the engineering open house. Free popcorn was provided by the local branch of the ACM.

No Quicksort? (4, Insightful)

gus goose (306978) | more than 3 years ago | (#33316032)

Feel like I'm complaining about a poll with a missing option, but, honestly ....:(

gus

Re:No Quicksort? (2, Funny)

maxwell demon (590494) | more than 3 years ago | (#33316164)

I also noticed that they have Gnomesort, but not KDEsort. :-)

Re:No Quicksort? (1)

jgagnon (1663075) | more than 3 years ago | (#33316858)

What would an XKCDsort look like?

Re:No Quicksort? (2, Informative)

Apocryphos (1222870) | more than 3 years ago | (#33317272)

Like shit.

Re:No Quicksort? (3, Insightful)

kvezach (1199717) | more than 3 years ago | (#33316210)

No thinking outside of the box -- no radix sort? Seriously!

Re:No Quicksort? (3, Funny)

Tanktalus (794810) | more than 3 years ago | (#33317148)

I was looking for Bogosort [wikipedia.org] myself, actually.

Re:No Quicksort? (0)

Anonymous Coward | more than 3 years ago | (#33317162)

And no Bogosort? Or Stoogesort? LAAAAAME!

Re:No Quicksort? (1)

tepples (727027) | more than 3 years ago | (#33317170)

Quicksort is the special case of radix sort with 2 bins.

Re:No Quicksort? (0)

Anonymous Coward | more than 3 years ago | (#33317484)

No it's not. Otherwise Quicksort would not be O(n log n) and radix sort would not be O(n). Radix sort is sorting and then saying "well, I don't need to sort these bins, too."

Re:No Quicksort? (0)

Anonymous Coward | more than 3 years ago | (#33318548)

Well, almost.. In-place binary MSD-radix would be pretty close but standard quicksort uses data-dependent pivots.

Shear Sort (3, Insightful)

jellomizer (103300) | more than 3 years ago | (#33316038)

The Shear Sort is one of my favorite sorts out there. Although you will need an orchestra to play it.

Re:Shear Sort (0)

Anonymous Coward | more than 3 years ago | (#33316484)

after reading about shear sort, I envision a waltz.
http://everything2.com/title/shear+sort

Re:Shear Sort (1)

Abstrackt (609015) | more than 3 years ago | (#33317364)

The Shear Sort is one of my favorite sorts out there. Although you will need an orchestra to play it.

And a wind tunnel.

Excellent (1)

schlick (73861) | more than 3 years ago | (#33316088)

That is awesome.

Re:Excellent (0)

Anonymous Coward | more than 3 years ago | (#33316274)

It's sort of cool.

Re:Excellent (0, Troll)

Blakey Rat (99501) | more than 3 years ago | (#33316616)

It was pretty awesome when I did it on my C-64 back in 1990 too. But I didn't have YouTube then, so I couldn't attention whore as effectively as modern programmers.

Re:Excellent (0)

Anonymous Coward | more than 3 years ago | (#33316686)

You're attention whoring right now, only problem is you've done shit all so stop raining on this guy's parade.

Just Play Popcorn by Hot Butter (1, Insightful)

Anonymous Coward | more than 3 years ago | (#33316112)

It doesn't even matter if it matches the sorting. All sorting algorithms will benefit from the playing of Popcorn.

Try it with people (5, Funny)

twoshortplanks (124523) | more than 3 years ago | (#33316130)

It's always more fun to do this with real people (sort by height, for example). The London Perl Mongers tried this as a drinking game: You get enough people down the pub (or, in one this case, outside a bar in portugal during conference season) and apply booze. Then bubble sort them as a group (lots of shouting Stay! Switch!.) Add drinking penalties when people screw up the algorithm. You get the idea.

There's a video on the internet somewhere. Free pint to the first person to find it.

Re:Try it with people (1)

Inda (580031) | more than 3 years ago | (#33318158)

A variation we've played is to sort the line on age, but you're not allowed to say numbers and month names.

Re:Try it with people (2, Funny)

siriuskase (679431) | more than 3 years ago | (#33319694)

No way, I don't want to stand near a guy who's only 5' 4". That's normal for women, but guys like that tend to have defective personalities. I like to stand near the tall guys.

Not boring, more interesting (1)

decipher_saint (72686) | more than 3 years ago | (#33316144)

There was a dismissive comment recently modded down about being "easily amused" by the bleeps and bloops, well that may be so, but it sure adds flavor to the process.

I can imagine how various sorting operations work in my head but I never thought about what they might sound like, and that makes them just a little more interesting. :-)

Re:Not boring, more interesting (1)

amRadioHed (463061) | more than 3 years ago | (#33317062)

I never thought about what they might sound like either, but now that I know what they sound like I can't help but wonder what they might taste like. I'm betting quicksort tastes just like snozzberry.

Re:Not boring, more interesting (0)

Anonymous Coward | more than 3 years ago | (#33317440)

I'd wager bubble sort tastes like cactus needles and bee stingers!

As a decided non-expert... (2, Interesting)

KingAlanI (1270538) | more than 3 years ago | (#33316156)

One thing this seems to show me (at least the video does)
the rate of completion - how much is sorted by each point in the process
the algorithms seem to all do that a bit differently; some have most of the work completed in the beginning, some in the end.
Most seem to take one piece of data and plunk it right in order; the merge sort seems to be the only one with intermediate groupings.
and there's one final pass to make sure the data's in order.

I notice different sorting processes are appropriate for different RL sorting situations.

Re:As a decided non-expert... (4, Informative)

pjt33 (739471) | more than 3 years ago | (#33316360)

The heap sort actually has intermediate structure. If you watch carefully you can see that it has two phases, the first much shorter than the second. However, the structure isn't as visibly obvious as for merge sort.

If it had showed quicksort (I can't understand why it didn't) then you'd have seen some intermediate structure there too.

I also noticed that the selection sort wasn't as good as it could be. It's more efficient to select the largest and the smallest unsorted values on each pass - you halve the number of passes, and on each pass you do 50% more work, so overall it's a 25% improvement.

60s/70s music (1)

suso (153703) | more than 3 years ago | (#33316196)

A lot of them sound like something you'd hear at the beginning/end of some song from the 60s or 70s.

The sound of bubble sort (5, Funny)

Anonymous Coward | more than 3 years ago | (#33316218)

That's strange. When I listen to the sound of bubble sort all I hear is one of my college professors threatening to hunt me down and kill me in my sleep if I ever use it.

Re:The sound of bubble sort (1, Funny)

MrMe (172559) | more than 3 years ago | (#33316440)

That's strange. When I listen to the sound of bubble sort all I hear is one of my college professors threatening to hunt me down and kill me in my sleep if I ever use it.

I just hear my bong.

Re:The sound of bubble sort (2, Informative)

Anonymous Coward | more than 3 years ago | (#33316850)

then your profs are kinda dumb, there are plenty of times when its acceptable to use bubble sort....

suppose you are on an embedded device, and you know that your inputs will always be limited by some factor, bubble sort also has rather good cache performance

Re:The sound of bubble sort (1)

lewiscr (3314) | more than 3 years ago | (#33316904)

Bubble sort does have it's uses; if you know the array is <= 3 elements, Bubble Sort wins.

Re:The sound of bubble sort (2, Interesting)

jfengel (409917) | more than 3 years ago | (#33317742)

And that's not uncommon. There are plenty of circumstances where you may have a large number of short lists floating around. Say, a list of a person's children, which will be less than 4 in 99% of cases and even the extreme cases aren't going to kill you. There may be many instances of the list, but each will be small.

Sorting those lists via some O(n^2) sort is lower overhead than building up fancy data structures. Especially if you're building the lists incrementally, such as via an insertion sort (much like an incremental bubble sort).

Re:The sound of bubble sort (1)

Joce640k (829181) | more than 3 years ago | (#33317986)

Yep, I've seen optimized implementations of quicksort which drop down to bubble sort when there's only three or four elements in the current subdivision.

PS: The one in the video could easily be optimized to go twice as fast and would beat some of the others if you did.

Re:The sound of bubble sort (0)

Anonymous Coward | more than 3 years ago | (#33318034)

It also parallelizes to O(N) time if you happen to have N processors.

Re:The sound of bubble sort (1)

sconeu (64226) | more than 3 years ago | (#33318454)

The bubble sort one actually did sound kind of bubbly.

Could be Better (1)

Evets (629327) | more than 3 years ago | (#33316242)

I'm not a big fan of these sounds, but I like the idea.

Merge Sort - traffic sound
Bubble Sort - blowing bubble sound from bubble bobble
Insert Sort - coin slot
Select sort - crain game sounds
Gnome Sort - 7 dwarfs singing Hi-Ho, Hi-Ho

At least that way you can associate sounds with different algorithm types and remember what they are.

Sounds for Dr. Who (0)

Anonymous Coward | more than 3 years ago | (#33316260)

Any one see this as some sound files for the BBC Dr. Who Series.

Hardly new (1)

by (1706743) (1706744) | more than 3 years ago | (#33316294)

My CS lecturer [stanford.edu] prepared a number of these for an intro CS course. I took the class back in '06-'07, but IIRC the videos were taken from Mac OS X. That said, it is pretty neat.

Re:Hardly new (1)

by (1706743) (1706744) | more than 3 years ago | (#33316948)

...Mac OS X.

Gah, meant Mac OS < X

Diagnostics (4, Interesting)

PPH (736903) | more than 3 years ago | (#33316308)

One interesting application of such audible/visual representations could be for diagnostic reasons.There are numerous cases where experienced observers can spot patterns or anomalies in patterns that machine algorithms have trouble with.

One example I was involved in years ago at Boeing was a tool for diagnosing a large switch matrix used in a piece of automated test equipment. Each output could be tied to a high, low or open signal, driven from a controller over an HPIB bus. Failure modes included not only an output stuck high, low or open, but address bus problems where some lines would cause passive failures or activate more than one pin. After watching a poor engineer go through a suspect matrix panel for over a day, entering a command on the bus, finding the pin on a patch panel, sticking a voltmeter on it, over and over a few thousand times, we came up with a solution. Bi-colored LEDs wired to a patch panel and a program to exercise the matrix with a series of address patterns. An observer could spot a single bad switch or a hung address bus line in a few seconds just by looking for an anomaly in a couple of checkerboard and other patterns.

should be marked NSFW (0)

Anonymous Coward | more than 3 years ago | (#33316316)

because i just got off to that geek pr0n

Clown Sort (1)

quatin (1589389) | more than 3 years ago | (#33316354)

My favorite sort. Randomly arrange items until they are in order. Would the appropriate music be some type of carnival melody?

Re:Clown Sort (2, Informative)

maxwell demon (590494) | more than 3 years ago | (#33316510)

I know this as bogosort. Wikipedia also mentions random sort, shotgun sort and monkey sort as alternative names, but not clown sort. Also a Google search for "clown sort" doesn't seem to give sorting algorithm results, not even if I add algorithm as additional search term.

Re:Clown Sort (1)

operagost (62405) | more than 3 years ago | (#33317652)

They probably mean bozo sort. You take two random items and switch them.

Bugged bubble sort? (2, Interesting)

Anaerin (905998) | more than 3 years ago | (#33316438)

The bubble sort used here is kinda bogus. It iterates over the whole set on every pass, which it doesn't need to. It only needs to go over dataset-(pass-1) items. I have a feeling this will change the "sound" of the bubble sort in this example.

Re:Bugged bubble sort? (2, Informative)

Anonymous Coward | more than 3 years ago | (#33316842)

That optimization doesn't change the run-time complexity of the algorithm, it's still O(n^2). Usually bubble sort is taught without the optimization and once the student understands, you point out that particular optimization or try to get them to figure it out on their own.

Re:Bugged bubble sort? (1)

BitterOak (537666) | more than 3 years ago | (#33319190)

That optimization doesn't change the run-time complexity of the algorithm, it's still O(n^2). Usually bubble sort is taught without the optimization and once the student understands, you point out that particular optimization or try to get them to figure it out on their own.

I haven't yet run across a comp. sci. text that describes the bubble sort without the "optimization". I've always thought it was an intrinsic part of the bubble sort algorithm.

What Fun! (1)

PocariSweat1991 (1651929) | more than 3 years ago | (#33316474)

The Selection Sort's soundtrack was quite fun!

It feels like your head is going to explode at the end, and the final pass is the sound of brain matter splattering across the pages of your algorithms textbook.

Visual Aids (1, Interesting)

Anonymous Coward | more than 3 years ago | (#33316522)

I found http://www.sorting-algorithms.com/ to be useful for looking at how sorting works, too.

Also fun: porttwiddle (1, Interesting)

Anonymous Coward | more than 3 years ago | (#33316558)

http://wolfbell.com/projects/index.html [wolfbell.com] - Porttwiddle is an add-on module to a one-disk linux router project that will play sounds of different frequency depending on the port number. You'll never miss a portscan again! ;-)

Sorting is fun (1)

operagost (62405) | more than 3 years ago | (#33316596)

I sorta like it.

Which sounds best? (1)

kabloom (755503) | more than 3 years ago | (#33316638)

They should bring back the Slashdot poll to discuss which of these sorting algorithms sounds best. (IMO, Insertion sort, bubble sort, and Heapsort sound coolest.)

Re:Which sounds best? (1)

treeves (963993) | more than 3 years ago | (#33316938)

I liked selection sort the best. Musically, the "piece" constantly seems to accelerate leading to a pleasing conclusion. But merge sort was a more complex piece.

Very Old Idea (1)

canajin56 (660655) | more than 3 years ago | (#33316646)

The sounds aren't quite the same, but Quick Basic for MS DOS had a program in the Examples folder that does almost exactly this. Generates random data and shows various sorting techniques on it visually, playing a different tone for each comparison made. Not as much data (since it had to graph it in 320x200), much slower in a 286, and sound was done by internal speaker, but same idea at least.

sort video memory (0)

Anonymous Coward | more than 3 years ago | (#33316736)

A tutor once filled text mode video memory (DOS days, no memory protection) with the solid block character in random colours, then sorted said video memory with bubble sort, heap sort, shell sort and quick sort. In other words, the coloured blocks sorted themselves on screen. Remarkably effective demonstration of the relative speeds and of how the algorithms work.

Sorting is a waste of time (1)

mmaniaci (1200061) | more than 3 years ago | (#33316760)

Meh, sorting should be covered in about 2 hours in any programming course. I spent an entire quarter on sorting back in college and I still to this day cannot see the point of repeating the same exercise over and over again, just with a different sorting algo. But perhaps my professor was just retarded (that was the general consensus between the students anyway).

WTB New slashdot CSS/JavaScript programmer. The current one really blows.

Re:Sorting is a waste of time (5, Insightful)

mea37 (1201159) | more than 3 years ago | (#33317024)

If you think all that time examining sorting algorithms was intended to teach you about sorting, then you indeed missed the point. Programming courses spend a lot of time on sorting because it is a common task that can be easily understood, but for which there are a lot of different algorithms with very different performance characteristics. The point is to teach algorithm analysis skills.

Judging from the quality of code I encounter regularly, though, you're far from alone in failing to pick up that lesson.

Re:Sorting is a waste of time (1)

rrohbeck (944847) | more than 3 years ago | (#33317848)

Exactly. The only time I ever looked at sorting algorithms was in university. For the last 20+ years, all I ever did was call some sort() or qsort() library function.
Considering whether to apply a Schwartzian Transform was probably the most I ever thought about sorting.

Re:Sorting is a waste of time (1)

clone53421 (1310749) | more than 3 years ago | (#33317974)

The point is to teach algorithm analysis skills.

Well, that, and to teach that their performance isn’t the only metric that you can judge them by... for instance, the “best” (fastest) sorting methods also tend to be the most inefficient in terms of how much extra memory they need. If you swap elements with XOR, a bubble sort only requires 1 extra bit to tell it when it’s finished.

sorting rules (1)

bhcompy (1877290) | more than 3 years ago | (#33316856)

Sorting may be boring, but it is an awesome way to really dive in to a language(at least c++).

Boring?? (1)

Tetsujin (103070) | more than 3 years ago | (#33316982)

I read Knuth for fun... I don't get this notion of algorithms being "boring"...

Fairly dry? (1)

sgraar (958944) | more than 3 years ago | (#33316992)

What do you mean it's fairly dry? Sorts are awesome!

Respect the sorting algorithms!

Re:Fairly dry? (0)

Anonymous Coward | more than 3 years ago | (#33317086)

My favorite (and most memorable) part of my high-school programming classes was learning the sorting algos.

Sorting real objects (3, Interesting)

spaceyhackerlady (462530) | more than 3 years ago | (#33317038)

As an undergrad I worked in the university library to earn a bit of spending money, and one of my tasks was sorting books to put them back on the shelves. My colleagues used selection sort. I didn't.

I did a first pass through the books. Two piles, typically A-L, M-Z. Then a second pass, A-D, E-L, M-R, S-Z. And so on, until the piles were small enough I could go through them and put them on the shelf in order.

How many people do you know who actually use quicksort to sort real objects?

...laura

Re:Sorting real objects (1)

SpeedBump0619 (324581) | more than 3 years ago | (#33317684)

Well, to be pedantic, that's not *strictly* quicksort. It's a two bin radix sort. The only difference, of course, is that in quicksort you pick your pivot based on some item(s) in your set, and in radix you select the boundary based on properties of the data distribution. I only mention it because I *have* seen something that uses radix sort on physical objects: an old punch card sorter.

Re:Sorting real objects (1)

rrohbeck (944847) | more than 3 years ago | (#33317942)

I always used a variation of the aptly name Library Sort: Throw all the books on the floor and then put them roughly in the right position on the shelf, leaving gaps. After all, you have almost infinite scratch space.

Re:Sorting real objects (1)

clone53421 (1310749) | more than 3 years ago | (#33318524)

I always do an insertion sort until it starts getting inefficient (pretty soon usually) then abandon my sorted stack and start a new one. Once I have sorted everything into small sorted stacks, I merge sort them two at a time to get larger sorted stacks, then repeat until I have only one sorted pile.

Re:Sorting real objects (0)

Anonymous Coward | more than 3 years ago | (#33319814)

i'm going to sleep soundly tonight since learning i've been quicksorting all my life :-)

What about Random Sort (1)

ookabooka (731013) | more than 3 years ago | (#33317040)

What about random sort, where you swap 2 random values and test to see if it is sorted. I assume it would sound like static, probably white noise (as opposed to pink noise).

Re:What about Random Sort (1)

clone53421 (1310749) | more than 3 years ago | (#33318422)

I would optimize that by only swapping the values if they’re out of order:

<html>
<body>
<canvas id="paintbox" height=480 width=640 />

<script>
function sorted(a) {
    for (var i = 0; i < a.length;) if (a[i] > a[++ i]) return false;
    return true;
}

function sort_values() {
    if (!sorted(a)) {
        var i = (Math.random() * (a.length + 1)), j = (Math.random() * a.length), t;

        if (j >= i) j ++;
        else { i ^= j; j ^= i; i ^= j; }

        if (a[i] > a[j]) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;

            canvas.clearRect(i, 0, 1, 480);
            canvas.fillRect(i, 480 - a[i], 1, a[i]);
            canvas.clearRect(j, 0, 1, 480);
            canvas.fillRect(j, 480 - a[j], 1, a[j]);
        }

        var t = setTimeout("sort_values();", 10);
    }
}

var a = new Array();

try {
    var canvas = document.getElementById("paintbox").getContext("2d");

    for (var i = 0; i < 640; i ++) a[i] = Math.floor(i / 640 * 480);
    for (var i = a.length - 1; i > 0; i --) {
        var j = Math.floor(Math.random() * (i + 1));
        a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j];

        canvas.fillRect(i, 480 - a[i], 1, a[i]);
    }

    var t = setTimeout("sort_values();", 10);

} catch (e) {
    alert("Get a better browser!");
}
</script>
</body>
</html>

(Bonus points if you knew what i ^= j; j ^= i; i ^= j; does without thinking about it too hard. Those are bitwise XOR operations, in case anyone didn’t know.)

fr1st psOt (-1, Offtopic)

Anonymous Coward | more than 3 years ago | (#33317068)

simple 5olution If you answered

Really? (1)

Radtoo (1646729) | more than 3 years ago | (#33317570)

I do not think the sound adds anything, myself. The visuals could be helpful if played more slowly, but the sound? It does not help me, and as used in TFA, it is even an annoying noise.

Actual code and performance analysis shouldn't be boring or "dry" to someone who aspires to be a computer scientist or specifically a programmer, especially not the first time they learn about it...

Re:Really? (1)

pclminion (145572) | more than 3 years ago | (#33318216)

I do not think the sound adds anything, myself. The visuals could be helpful if played more slowly, but the sound? It does not help me, and as used in TFA, it is even an annoying noise.

An old boss of mine used to work on a large computer which was used to control the activities inside a sawmill. It was made up of several thousand magnetic reed relays to perform the logic. The program itself was keyed into the system via about 1000 throw switches. The entire machine was devoid of silicon. This was pretty "old school." When the "code" was updated and a bug was introduced, he was often able to diagnose the bug by listening to the buzzing, clacking and whirring of the relay switches opening and closing. Stuck in an infinite loop somewhere? That made a "bzzz chicka chicka brr brr bzzz chicka chicka brr brr" sound. Is bit 6 of the program counter register stuck at zero due to a wiring fault? Why, it goes "whacka chunka whacka chunka whacka chunka..." After months of experience, he was able to characterize the internal state of the control program simply by listening to the sound of the machine. Don't discount the value of all possible input modalities when trying to understand how something works.

Listening to music (1)

EkriirkE (1075937) | more than 3 years ago | (#33317740)

I was listening to some dance/trance music. I though I had a problem with my speakers playing the video because I didn't notice any new sounds :o

Possibly the easiest C sort for arbitrary types (1)

Flector (1702640) | more than 3 years ago | (#33318806)

Still possibly the easiest (C++) sort for arbitrary types:


#include <vector>
#include <algorithm>
#include <functional>

class my_type
{ public:
int item_data;
};

bool isless_my_vector (const my_type ref1, const my_type ref2)
{ return ref1.item_data < ref2.item_data ? true : false; };

int main ()
{
std::vector some_vector;

// populate some_vector
my_type item;
item.item_data = 5;
some_vector.push_back (item);
item.item_data = 10;
some_vector.push_back (item);

std::sort (some_vector.begin(), some_vector.end(), std::ptr_fun (isless_my_vector));

for (std::vector::iterator iter = some_vector.begin(); iter != some_vector.end(); iter++)
{
item = *iter;
// do something with item
}
return 0;

}


It's more efficient if the vectors holds pointers instead of data.

Boring? (1)

StikyPad (445176) | more than 3 years ago | (#33319046)

Sorting may be boring to implement repeatedly (tedium by definition), but I found learning the various standard sorting algorithms to be pretty interesting, and a great practical introduction to pointers.

Programming is first and foremost about problem solving, regardless of whether you're creating a game or a spreadsheet, and sorting is a common problem. If you find learning (and discovering) how to solve problems effectively and efficiently to be boring, then you're probably pursuing the wrong line of work.

If the implementation was written in C (1)

broknstrngz (1616893) | more than 3 years ago | (#33319272)

the authors should listen to Franz Schubert's Symphony Number 9.

Where are the llamas? (1)

knarf (34928) | more than 3 years ago | (#33320082)

Nice vids but where are the llamas [wikipedia.org] ?

For all you young whippersnappers: these sounds resemble the noises emanating from a series of C=64 games by Jeff 'Yak' Minter [wikipedia.org] , one of the better known software developers from the 80's.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...