Sorting Algorithms Introduction Introduction

It's a dark, chilly morning in Shmoopland, and you're on the first bus out to visit Great Aunt Nelly. The man to one side of you with indescribably bad breath keeps turning your direction to talk to the woman who's bumping you with her shopping bags from the other side.

Auntie Nell lives a solid four hour bus ride away, so…yeah. Time for some music.

You turn on your "90s Country Pop" playlist (don't deny it), mindlessly skipping track after track, when you realize that Past You had, uh...questionable taste in music. Time to get to deleting.

You could go through the songs one by one, deciding which to keep (hello, Shania) and which to toss (sorry, the guy who won American Idol that year), but you have 4,527 songs on this playlist. Unless you're willing to donate the better part of a year to that project, nobody has time for that.

But then you remember that the device has been Big Brothering you, and it's rated every song based on how often you listen to it. Creepy? Yes. Helpful? Also yes. Now that you have a way to compare them, you have a way of easily knowing the songs to delete. But how do you sort them so that you can separate the to-be-deleted songs to make the process faster?

You've just stumbled onto one of the most important parts of computer science: sorting. Think of the amount of information a computer has to store. In order to ever be able to access any of that information, it better have a good way of sorting it, right? Right.

Enter sorting algorithms.

Sorting algorithms are like the professional organizer who gets your hoards of information into shape without making you lift a finger. If we didn't have sorting algorithms, it would take for-stinkin'-ever to find anything.

Just like for everything in life, there are good ways and bad ways to do it. There are some really terrible ways to sort lists (we're looking at you, Monkey Sort), but we're here to tell you how to get it done right.

And then you can continue jamming to Shania.

 

Why Should I Care?

If the sheer joy of a list well sorted doesn't quite do it for you—"yeah, yeah, so they sort stuff; I want to know how sorting algorithms will help me"—you're in luck. Sorting algorithms are a great introduction into run time analysis, which tells us how long a program could run if we gave it billions of items. That's heavy info, too. Think about it: we need to know how efficient a program is. Otherwise, we could be waiting weeks to get an answer we expected to have in minutes.

And we're just not that patient.

If you know the syntax of a language, you can program. But to program well, you best become a master of run time efficiency, rising above the term code monkey.

It all starts with sorting algorithms. Doesn't it always?