What should students be taught first when first learning sorting algorithms?

Question

If you were a programming teacher and you had to choose one sorting algorithm to teach your students which one would it be? I am asking for only one because I just want to introduce the concept of sorting. Should it be the bubble sort or the selection sort? I have noticed that these two are taught most often. Is there another type of sort that will explain sorting in an easier to understand way?

Answer 1

If you want to teach sorting, then a bubble sort is probably the easiest to comprehend. If you want to teach sorting algorithms, then you should really be teaching quicksort, mergesort, insertsort and possibly even heapsort so that students can get a feel for the tradeoffs between various sorting methods.

Answer 2

No matter what sorting algorithm is taught, if the students don't also learn about bogosort, they're missing out, and the teacher is losing an obvious way of engaging his audience :)

Answer 3

I would teach the "call the framework" sort.

It would be efficient to teach and learn this sort. Students would have a high degree of success and low error rate with implementing this sort.

---

Edit: There are a lot of criticizing comments on this answer about the quality of my single sort class. These criticisms are applicable to any answer to this question, which is - "If you were a programming teacher and you had to choose one sorting algorithm to teach your students which one would it be?"

Answer 4

Bubble sort is the classic, and it is very easy to grasp why it works.

But unless this is a very introductory course then it should include an overview of other sorting algorithms since this is by far the best way to show the trade offs involved in algorithm design and explain best case vs worst case vs average behaviour (both runtime and memory).

Answer 5

I learned Bubble Sort first -- I think if you do only one, you probably need to do one of the O(n^2) algorithms because they are easier to understand.

There are a lot of sort visualizers out there to help quickly show a comparison:

• http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
• http://math.hws.edu/TMCM/java/xSortLab/
• http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html
• http://maven.smith.edu/~thiebaut/java/sort/

Answer 6

best lecture I ever attended on algorithms demonstrated all of them as bar-graphs drawn via java applets. You could then see the pattern of sorting as well as the O(N) characteristics as well...

Teach bubble because its incredibly simple and show the rest as animations maybe?

Answer 7

Selection sort is probably the most straightforward sorting algorithm to teach and simplest to grasp. It's also a great example of why simple solutions are not always the best, which could lead into a discussion of more interesting and faster sorts like mergesort and quicksort.

Answer 8

I think sorting methods are a very good example of what an algorithm is. But it only becomes a good example when you compare various methods. If you can only teach one, I'm not sure it's worthwhile.

Realisticly, we call the sort method in some framework. So if you can't effectively teach about the sorting alorithms, it might not be worth the time.

Nobody has to write a sort method anymore, but it's still a very good example of the impact of algorithms.

Answer 9

Uhm... sorting algorithms are really a intuitive, concrete way of teaching some good lessons about Big O notations, optimization, common sense and computer science in general, and maybe a "bubble sort" + "select sort" + "merge sort" approach might be useful, for comparison. I think the most intuitive (and efficient in many cases) is the select sort.

Answer 10

Bubble sort is the easiest one for beginners to grok, and it also serves as an excellent example of why easy solutions can be expensive. Could be a good way to segue into asymptotic complexity and big-O notation?

Answer 11

I'd teach Bubble sort if I had to pick only one, since it's simpler to grasp (I think). However, the most valuable thing I got out of studying the various sorting algorithms was that there's more than one way to do it (which eventually led me to Perl, but that's another story), each with advantages and drawbacks. So, learning a single sorting algorithm might be a way to miss the critical aspect of the whole thing.

Answer 12

Quicksort is definitely another very simple-to-understand sorting algorithm, and it's a cinch to implement it. It has in-place amd "out-of-place" versions that are fun to think about. And it's quick.

Quick enough for you, at least, old man.

Answer 13

I thought selection sort was the simplest to comprehend, and IMO would be the best to introduce sorting.

I think it would be silly to not teach them at least one O(nlog(n)) sorting algorithm, along with an explanation of big O notation.

Answer 14

I'm not sure I could be a computer science teacher and only teach one sorting algorithm.

At a bare minimum the students should be taught at least one of each of the major sorting types, namely an exchanging sort, a selection sort, an insertion sort, and a merge sort. In addition to one of each of these types, I would also cover Quicksort which falls under the partitioning sort heading.

As for the specific sorts from each of the types that I would cover:

• Bubble Sort as an example of the exchanging sort category as it is one of the simplest sort types and one that they likely have already seen or stumbled across on their own. This is also the sort they will most likely use the most often if they have to roll their own for something simple so it makes sense for them to understand it.
• Heapsort from the selection sort category. This would likely be the most confusing sort next to Quicksort but once they understand how it sets them up for understanding the Quicksort algorithm.
• Insertion Sort as an example of the insertion sort category would be covered as it is also a simple sort that they can get a lot of use out of. Since they might encounter scenarios where they need to merge two lists together, knowing this one makes sense.
• Merge Sort is somewhat of a specialized sort so you don't see it too often, but it is very good at what it does and is still useful in situations where you need to sort data that you are getting in a piecemeal fashion.

If I had to narrow things down to just one sort that I could teach, but I had the time to make sure that the student understood exactly what was going on then I would teach Quicksort. While it is not easy to grasp, the vast majority of frameworks out there use it for their sorting algorithm so an understanding of how it works is useful in your development with that framework. Also, it is quite likely that if someone is able to understand Quicksort then they should be able to learn the Bubble Sort and Insertion Sort on their own.

Answer 15

Er, you should be giving them an O(n^2) and an O(n log n) sort. Bubble and Heap would be my picks.

Answer 16

Regardless of the actual algorithm you'll choose, I advice you to present two algorithms (instead of one) and explain tradeoffs (in memory, execution speed, etc) they make.

Then you should hammer it down that there is no such thing as an ideal sorting algorithm that could be blindly applied to any task. There are good candidates, however. At this point, show them quicksort and introspection sort (as homework) and conside your task competed :)

Answer 17

Keeping in mind that your student will probably never have to code a sort themselves, the question really should be decided on "what is the value of learning this algorithm?" instead of "what does this algorithm do?"

In other words, your students should be taught a variety of different algorithms -- whether they are for sorting, searching, compressing etc is largely irrelevant.

Answer 18

I'd start by showing insertion sort. Everyone who's sorted a hand of cards (which is basically everybody) knows this sort. Plus it's doesn't have the abysmal performance of bubble sort.

Answer 19

IntroSort is a great algorithm to teach as well, once students have learned to understand Quick and Heap sort. IntroSort (short for Introspective sort) starts as a QuickSort and switches to a HeapSort if the recursion depth exceeds a level based on the logarithm of the number of elements being sorted.

Overall, you get the best of the Quick and Heap sort worlds and a worst case running time of O(n log n).

IntroSort on Wikipedia

Answer 20

I think that only teaching one sort is crippling. Remember that Everything Is Fast For Small n, so in terms of teaching a sort, it is not a question of performance, but understanding the algorithm.

I think the intro should be the bubble sort to introduce the concept, but at a minimum introduce another sort to get the students thinking about other ways to perform the task. Make sure they understand the tradeoff in performance and code complexity and that there are different tools for different situations.

Answer 21

I would compare and contrast an o(n-squared), like selection sort with a o(n log n) sort like quicksort.

But if they aren't computer science people and don't necessarily intend to be then just show an easy to understand sort like selection or bubble.

Answer 22

It would be radix sort. Because it is surprisingly easy and yet non-obvious. Things like that just have to be taught.

Answer 23

I would advise both Selection and Merge Sort on the general sorting algorithms. Both are relatively straight forward compared to their friends. But if you can only teach one and the people can handle it, I would go with Merge Sort. Because merge sort is efficient, stable, and teaches several important concepts (merging, divide and conquer).

Selection Sort:
Find the minimum/maximum value and put it in place, then do it again on the rest of the list...this is very intuitive. For me selection is much more intuitive than even bubble sort. You could probably teach this in very little time. And there will be a feeling of accomplishment by people implementing this... Although Bubble and Insertion can quit early and will not waste time on a sorted list. Selection is probably the easiest to do. Insertion is probably the hardest to implement.

MergeSort:
This will teach how to merge (which is important because there are a ton of speedups you can get by merging two sorted lists together) as well as how to divide the problem into smaller sub problems (important for dealing with hierarchical structures and also used in quick sort). QuickSort though faster is much harder to understand. You need two scanning variables, a pivot item, etc... Merge is more straight forward and merging will come in handy for things other than sorting (like joining two records together that are sorted on a field)....

The basic concept of a merge is intuitive. Take the lesser item from a sorted list and put that in the final list. And dividing the merge sort problem up is also kind of intuitive.
mergesort(first half) mergesort(second half)
merge (first half, second half)

If you can only teach one sort and have to do it quickly (or the audience isn't really interested at all) I would tend towards Selection because this is harder and selection could be taught quickly. But if the audience is more motivated then I would do Merge because it teaches so many additional fundamental concepts.

Of the more efficient sorts this one is much easier than quick and heap sort. Although quick sort is probably the quickest in practice (as long as you have plenty of ram) and heap is probably able to sort the largest lists (if implemented non recursively).

Bucket Sort:
I would touch on this because it is also intuitive and represents another type of sorting algorithm. In many situations this is appropriate and the O(n) time is very attractive.

Counting Sort:
It has its uses. There are some cases where this is very efficient...It is also relatively easy.

Answer 24

I just did that last week with my kid I ask him to come up with their own sorting algorithm, and asked how long it would take to sort a deck of cards using his method. Then I showed him Bubble Sort ( the easiest to explain to a kid) " It's a bubble!" and made him count the steps again. He realized then it was easier and faster.

Then If you want you can teach more advanced ones ( Quicksort is the most surprising ), Ideally you should teach three at least that are different ( not variation of the same)

Answer 25

Have everyone bring in a deck of cards, and pick out one suit. Divide into teams of two. One shuffles the 13 cards, and lays them face down in a row. The partner gets to point to two of the cards. The other picks them up, looks at them, and either says "In order" or "Not in order" The parter then can tell him to swap them, and lay them down again (face down)

The job of the partner is to sort the cards in order (something you will need to define up front).

When the parner thinks they are sorted, he says "Stop". The other turns the cards face up, and they check.

When this is done, discuss what worked for everyone. Then talk about BUBBLE SORT vs SELECTION sort

Then talk about QUICK SORT.

Have them try each of them out, with their suit of cards.

Answer 26

If you can ultimately only teach ONE algorithm at all, I think SelectionSort is even easier to teach (and implement IMHO) as BubbleSort. It might be ultra ineffectively, but everyone will get its concept, everyone with a little programming knowledge can read its code and there is one thing that makes SelectionSort rather unique among all sorting algorithms: It only needs n - 1 swaps for a list of n entries :-) Not only that it never needs to make more than n - 1 swaps, it actually needs exactly n - 1 swaps. The number of swaps performed is 100% deterministic and known before it even starts. I think this is not true for any other in-place sorting algorithm (though people are free to correct me in comments).

Otherwise I vote for BubbleSort and SelectionSort, those are easiest to understand and show how sorting the easy way (these are simple enough, students may actually come up with these solutions without ever having heard of any sorting algorithm) is sometimes not very effective. In contrast I'd show QuickSort and MergeSort, being very good divide and conqueror algorithms and both also very fast.

Algorithms I'd not use, as their concept is harder to get, are ShellSort, RadixSort, HeapSort, and BucketSort. Also they are rather special (you usually only use them when sorting certain kind of data or if you have certain constrains for sorting).

You might mention the little sister of ShellSort, InsertionSort (which is basically a shell sort where the step width has finally reach one), but only because many QuickSort implementation use InesrtionSort as fall-back sort, once the recursion gets too deep (or the remaining data set to sort recursively gets too small)... but here it starts getting really complicated and you shouldn't make it too complicated.

Answer 27

If you want to teach the concept of sorting, then I believe you must teach at least two different ways of sorting -- otherwise the students will think that sorting is just about the one way you taught them.

I think the students would get the most value out of learning a classic O(n^2) algorithm (preferably insertion or selection sort, but please not bubble sort, which has no justification for being used in real applications), as well as a divide-and-conquer, O(nlogn) algorithm such as quicksort or merge sort.

If you're worried that these sorts will be too hard to teach your students, have a look at these activities from Computer Science Unplugged, which are designed for elementary school students.

Answer 28

They should be first asked to implement their own sorting algorithm - from scratch, without reference to any existing algorithm beforehand. Doing this will teach them about sorting way more than telling them of an algorithm that they wouldn't have any idea how it was derived.

Answer 29

Let your students decide.

Before introducing any sorting algorithms, give each student some playing cards, maybe 10 or so. Then ask them to sort the cards. Have them write down the steps they take, which will essentially be their algorithm. Likely they'll discover insertion or selection sort. You can also ask them to estimate how many steps their sort would take if they had 100, or 1000 cards, which is a good lead into big O notation.

PS - does anybody think they'd discover bubble sort?

Answer 30

i think the movie Sorting Out Sorting, which was produced 30 years ago, is still a pretty good instructional aid in gaining better understand of sort algorithms .. heres the 12x speed version

Answer 31

Start with insertionSort, then move on to mergeSort, quickSort and heapSort, avoid bubbleSort (there are tons of studies which show that insertionSort isn't that much harder to understand/implement, and in contrast to bubbleSort it has a practical use (faster on small arrays than mergesort e.g.).

Answer 32

Don't forget Spaghetti sort... get ready for Quantum Computing :-)