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
- It saves programming time (your reputation and your customer's money).
- It's correct. It's surprisingly easy to write a sort with unobvious bugs.
- It's efficient. Writing a sort that is as fast would be unlikely.
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
[TO DO]