Thursday, October 5, 2006

Sorts

Topics

• O(n²) Sorts
• Sorts of O(n²) usually have two nested loops inside their algorithm, with the indexes walking up or down at least part of the array in each loop.
• O(n²) sorts are significantly slower than the O(n lg(n) ) sorts, but they are useful small amounts of data because their algorithms are very simple to implement.
• Demonstration and analysis of Bubble Sort.  Bubble Sort is the slowest, but in its short circuit version it can be quite useful for certain types of data, particularly data that is already partially sorted.
• Demonstration and analysis of Selection Sort.  It is about 4 times faster than Bubble Sort, but there is no way to short circuit it, so for certain types of data it is much slower than Bubble sort.  It takes about the same amount of time no matter what the data is.
• Demonstration and analysis of Insertion Sort.  Also about 4 times faster than Bubble Sort, it also can not be short circuited.  It does, however, do well with partially sorted data, still usually beating Bubble Sort.
•  
• O(n lg(n)) Sorts
• Sorts of O( n lg(n) ) use a divide and conquer strategy.  They tend to divide the size of the sort into halves, then fourths, then eighths, then sixteenths, etc.
•  
• Demonstration and analysis of the Quick Sort.
• The Quick Sort algorithm calls itself recursively twice, hopefully dividing the current array into two approximate halves.  
• Since the two recursive calls can be sent unequal parts of the array, in the worst case the recursion is called n - 1 times and the Quick Sorts degenerates to O(n²).  Usually there is a stack overflow before the sort is finished.
• For totally random data, however, the Quick Sort is usually the fastest standard sort.
• There are a number of variations on Quick Sort.  Quick Sort is more efficient if the recursion is stopped early and the remaining data in each small portion is sorted by Bubble or Insertion Sort.
•  
• Demonstration and analysis of Shell Sort. 
• The Shell Sort algorithm uses two nested loops, but the index numbers are divided each time in the outer loop, instead of walking the entire array.
• Shell Sort achieves O( n lg(n) ) times, although this cannot be proven mathematically.  It is obvious from empirical studies, however.
• Shell Sort is about twice to four times as long as Quick Sort for most data, but it is highly stable and can be used on any data.
•  
• Demonstration and analysis of Merge Sort.
• The Merge Sort algorithm is recursive, similar to Quick Sort, but much less complex.
• Since the Merge Sort algorithm simply calculates the halfway point, instead of guessing as the Quick Sort does, it is usable with all kinds of data.  It does not degenerate to O(n²) with certain types of data.
• Merge Sort requires twice the memory of the Quick or Shell sorts, which can be done in-place.
• Merge Sort often beats Quick Sort, and is often used if the memory is available.
• There is an in-place Merge Sort algorithm, but it is much less efficient.    

Readings

Chapter 9, Section 9.1 and 9.3.