C++ Notes: Algorithms: Sorting

Arranging elements in some order is called sorting. Typically this is an operation applied to arrays or other indexable data structures.

Warning to students. Professional programmers do not write their own sorts functions. Why? They use the sort() function in the <algorithm> part of the STL library because

Is the time spent in classes studying sorting wasted? Sorting provides a lot of programming practice, and is considered a good introduction to Big-Oh issues. So maybe it's worth the class time. But take a look at STL sort for arrays for an introduction to using the library sort function.

Introductory Sorts - bubble sort and selection sort

Perhaps the two most common sorts for introducing sorting are bubble sort and selection sort. Both are simple and adequate for small amounts of data. Their O(n2) performance is not acceptible for large data sets. For faster sorts, O(n log n), already implemented in the library, should be used.

Bubble sort

Bubble sort compares two values next to each other and exchanges them if necessary to put them in the correct order. There are many variations on bubble sort, but they all examine adjacent pairs.

Students like bubble sorts -- could it be the name or the intuitive algorithm? Instructors also like bubble sorts, perhaps for the many interesting programming variations. However, the sad truth is that they often aren't very efficient. They should only be used with small arrays or almost sorted data.

Selection sort

Selection sort successively choses the largest (or smallest) value remaining in the array. While the performance on the average may be no better than bubble sort, it does allow for a significant reduction in the number of swaps, which can have a good performance effect on cache memory usage. On the other hand, it can not finish early if the data is already sorted.

Faster sorts

[TO DO - explain a little about the O(n log n) sorts, such as introsort, quicksort, heapsort, ...]

Using the STL sort

The sort() function in the STL library can be used with arrays and other data collections. The only description in these notes is STL sort for arrays.

Stable sorts