2209

32
+14  Q:

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

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?

+14  A:

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.

This is basically exactly what my algorithms class taught us.
Bucket sort is also a good one to learn
yes, yes, and yes. My canonical list would also include shellsort.A typical algorithms assignment is to benchmark solutions to each and see if they really match their theoretical Big-O (especially nearly sorted data on quicksort).
Bubblesort should not be taught, unless it is with the disclaimer "Never use this sort in practice".
Well yeah, it should always have that disclaimer :) Well, to my mind it should be more of a 'this should never be used on it's own in practice'.
+19  A:

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

how to sort badly. I like it.
FTA: "Bogosort ... is a particularly ineffective sorting algorithm". It is to teach the concepts of sorting, not something you or I would use in code.
A totally impractical sort, ah, the separation of science and craft.
Very interesting is that it is very difficult to implement properly.
@Terminus, you just keep checking if the set is ordered and if not you do a Knuth shuffle. How hard is that?
@Iceman, Terminus was perhaps referring to `quantum bogo-sort`; wikipedia points to details at jargon file (http://www.catb.org/~esr/jargon/html/B/bogo-sort.html)
@Unreason, I hope that's the explanation.
+2  A:

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?"

Great option for training programs in private, for-profit companies. Horrible option for CS programs. And I say that as being a former instructor for a private, for-profit company.
I understand why this answer was voted down, but in practice, it's really the best solution. If a colleague wrote their own sorting algorithm, I think I'd jump all over them. +1 for "lets show the students what they will actually be doing in a programming job"
Sorting algorithms are usually taught in an algorithm class. If I paid for a paper and they said 'call the framework', I'd ask for my money back.
You still need to understand what is going on in the sort that the framework implements - if you don't then you might encounter some issues in optimization of code.
People that only understand one sort algorithm should not be optimizing code.
It'd be a complete waste of educational time, suitable only for code monkeys that will never move beyond being code monkeys.
CS students are being taught how things work, not how to program. Also, with the law of leaky abstractions then you shouldn't be allowed to use this until you know what it is doing and understand where things are likely to go wrong ;)
I was going to make this suggesting, but figured it might get voted down :-).
I was going to make this suggestion. I had a direct observation on the matter: my co-worker had been teaching (unsuccessfully) the Bubble Sort (the worst possible choice) to one of our designers (a non-programmer). After sometime I've suggested her the "call the framework" method. It was a success.
Vlion, your comment could be an answer to the original question as easily as a criticism of this answer. Under what possible circumstances would you only want to teach one sorting algorithm? *Perhaps if you're just trying to train code monkeys?*
The problem is that this question is flawed. There is no reason why students should only be taught one sorting algorithm. If you go from the premise that you can only teach the students one way to sort, the only right answer is to use whatever sort the framework provides.
+1  A:

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

+5  A:

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:

A:

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?

+3  A:

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.

+3  A:

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.

This, definitely, is the real answer to this question. They don't teach sorting in CS classes because it's important for programmers to know how to write a sorting algorithm... they teach it because it's an incredibly useful way of showing the effects of different approaches to a problem.
+2  A:

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.

A:

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?

A:

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.

A:

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.

+1  A:

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.

+29  A:

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.

don't forget the 'one-pass bubble sort followed by quicksort' to remove that nasty worst-case quicksort :) (ironic that quicksort is slowest when used on a sorted list, but useful that this is bubblesorts quickest sort :))
This is a good answer, but I think merge sort should definitely be added to the list. It is a decent sorting algorithm and a good example of divide and conquer algorithms.
@Doug - Good point on the merge sort.
I would add bucket sort, since it's really a different idea with different tradeoffs compared to the others.
@tloach - True, but the Bucket Sort also isn't a comparison sort which tend to make up the majority of sorts out there.
@workmad3 - I would leave this for the students to discover during a discussion on how to improve algorithm efficiency - 'inventing' this concept usually requires out of the box thinking and can be a powerful Eureka moment for some...
Interestingly, those are precisely the 5 sorts that we covered in my uni class, if memory serves. :)
A:

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

A:

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

A:

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.

+6  A:

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.

Handing someone unsorted cards is also a good way of teaching the insertion sort as well. Once they grasp the fact they already did it before most people can translate it to code.
Bubble sort has O(N) best case, which is the best possible. There are cases where it will be the fastest (nearly sorted data), even if it generally shouldn't be used in practice.
For me insertion sort was the hardest of the O(n^2) sorts. Selection was easiest and bubble was a bit harder. Usually insertion has more shifting when implemented more efficiently which is harder than just exchanges.
A:

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

+2  A:

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.

Actually, Jeff is very, very wrong for some exponential cases (all real-world problems). For example, finding stable configurations even for *very* small molecules (n < 10 here!) may take hours on modern workstations.
True, but for the basic sorts (bubble, select, quick, etc), it is still valid for small n.
A:

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.

+2  A:

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

+2  A:

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.

+1 on merge sort. I know some people have difficulty understanding recursion, but I think merge sort can be conveyed sufficiently simply to make it understandable. Like insertion sort, it can be demonstrated with a deck of cards quite easily, too.
A:

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)

+1  A:

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

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

A:

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.

A:

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.

A:

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.

+9  A:

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?

I wish I could up-vote this more. There is nothing more pedagogically powerful than having students devise a method for doing something, and only _after_ doing that, showing them what other people came up with.
A:

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

A:

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

A:

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