Summary
Table 10.2 summarizes the characteristics of the sorting methods discussed in this chapter.
| Sorting Method | Average | Worst Case | Stable | In Place | Remark |
|---|---|---|---|---|---|
| Insertion | O(n^2) | O(n^2) | Yes | Yes | Good for few items and teaching purposes |
| Bubble | O(n^2) | O(n^2) | Yes | Yes | Good for teaching purposes and easily maintainable code |
| Shell | O(n^1.25) | O(n^1.5) | No | Yes | Good for general purpose and time-critical systems |
| Heap sort | O(nlog2 n) | O(nlog2 n) | No | Yes | Best for time-critical systems and large lists |
| Quick sort | O(nlog2 n) | O(n^2) | No | No | Best for many strings |
| Radix sort | O(m*n) | O(m*n) | No | No | Perfect for large lists with numbers |
Note that often interesting results can be gained by combining sorting algorithms. Think, for instance, of a quick sort implementation that calls insertion sort when it receives an array with a small number of elements or a sorting algorithm that uses radix sort for small keys and quick sort for longer keys. The best mix-and-match for you to use depends, of course, on the data set you are using and the way in which you want to use it. The best advice here is to experiment.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.