Tuesday, November 28, 2006

Searching & Sorting

Topics

O(n²) Sorts

• O(n²) Sorts are much less efficient than O(n lg(n)) Sorts, but they are easy to code and work well with small amounts of data (up to about 50,000 items).
• 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.
   
• Bubble Sort
• Very easy algorithm to understand and code, but otherwise inferior to the other sorts.  Can be improved with a technique called short circuiting, however, and then it works quite well with certain types of data
   
• Insertion Sort
• Usually takes half the time of Bubble Sort.  Can be very efficient with data that is nearly sorted already, but very inefficient with data that is reverse sorted.
   
• Selection Sort
• A little trickier algorithm to understand, especially if you are weak understanding array indexes.  About half the time of Bubble Sort under most conditions.  Always about the same time, no matter what the initial state of the data.  Very dependable algorithm, but there is no way to make it more efficient depending on the data.
   

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.
•  
• Quick Sort
• The Quick Sort algorithm calls itself recursively twice, hopefully dividing the current array into two approximate halves.
• The Quick Sort algorithm is the hardest of the algorithms to understand.  It's strategy is to guess at a half-way value, and then put all the values below that half-way value physically below the half-way value in the array, and all the values above that half-way value physically above the half-way value in the array.  This divides the problem into two smaller sub-arrays, which are then sorted with a recursive call on each sub-array.  
• Since the half-way point is a guess, if the guess is not good then the two recursive calls can be sent parts of the array that are very unequal in size.  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 Insertion Sort.
•  
• 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.
• It is essentially an Insertion Sort that starts with very wide jumps, and then uses increasingly small jumps, finally ending with a jump of 1, which is the same as regular insertion sort.
• It works much better than Insertion Sort because it gets the data close to its final position very quickly.  Then as the jump gets closer to 1, the array is in partial sort already, which is very efficient for the final Insertion Sort.
• 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.
• Shell Sort is not named after moving shells around.  It is named after its creator, Donald Shell.
•  
• Merge Sort.
• The Merge Sort algorithm is recursive, similar to Quick Sort, but much less complex.
• On the way down the recursion it does very little except recursively dividing the array into halfs, quarters, eighths, ...
• Coming back up the recursion is where all the work is done.  The two pieces, which are sorted by the recursion below, are combined into a single sorted array, using a second array in memory as the destination.
• 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.    

Other Sorts

• There are hundreds of different sorts, many designed for specific situations.
• Since input from a file is so much slower than internal processing of data in memory, you can often do a sorted linked list insertion of each piece of data while waiting for the next piece of data to arrive from the input.  In that case, an ordinary input, and a sorted input would take about the same time.  Walking the linked list would then give you the sorted data.
• You could also use a Binary Search Tree to sort your data.  A Binary Search Tree is an inherently sorted data structure.  You just create the Binary Search Tree and then do an in-order recursive transversal of the tree to read out the sorted data.
• Radix sort: This was a popular sort in the days of punched cards, but still can be used, especially for sorting mixed text and numeric data (sorted by its ASCII characters).  It is also very close to the way humans will sort objects.  First group all the data by its first character.  Then split each of those groups into subgroups based on the second character.  Then split each of the subgroups into smaller subgroups using the third character, and so on until each "group" is only one data item.  The data will now be in order according to the character values.  Radix sort is also done the other way, starting with the last character, then the next to last character, and so on.
   

O(n) Searches

• Searching through data by checking each data item until the correct item is found is the least efficient search.  It is called an O( n ) search.  The main advantage is that the search works the same whether the data is sorted or not.  Another advantage is the near trivial algorithm, a simple loop. 
• Simple linked lists require this type of search.  So do unsorted arrays.
• O(n) searches are normally avoided unless the number of data items is small, mainly because better searches are easily available.. 

O(lg n) Searches

• A Binary Search Tree, especially a reasonably balanced tree, is an excellent data structure for both inserting and searching for data. 
• If your data is in a sorted array, the Binary Search is an efficient and practical search algorithm.  You simply take the half-way index of the array, and compare the value there with the value you are searching for.  If they match, you are done.  If not, and the value you are searching for is less than the value at the half way index, then the value is in the lower half of the array.  If greater, the value is in the upper half of the array.  Treat whichever half you are using as an individual array and do the process again, using its half-way index.  Keeping dividing the array by half until you find the value you are looking for, or the "half" has zero length, in which case the value is not in the array.
• The Binary Search pseudocode looks like this:
  
  lowerindex = 0;
  higherindex = SIZEOFARRAY - 1;
  
  while (lowerindex < higherindex)
      halfindex = higherindex - lowerindex / 2 + lowerindex
      if searchvalue == value at halfindex then
           stop and return -- the value has been found
     else if searchvalue < value at halfindex then
           higherindex = halfindex - 1
     else
          lowerindex = halfindex + 1
  endwhile
  return the value was not found
   

O(1) Searches

• Some data can be organized for the most efficient possible searches O(1).
• If the data can be organized so that an index number associates directly with the data, then a search is simply accessing a member of an array.  This is why data is often given key numbers, such as your Parkland student number.. 
• Even if there is no simple way data can be indexed, there is a technique called Hashing that accomplishes much the same end.  Hashing is covered in the next course, Csc 220 Data Structures, along with a number of useful ways to organize data.  Csc 220 also will tell you what the silly O(...) means.
• The previous entry was a sneaky advertisement, yes, but we are a non-profit institution, so it would be better classified as a little bit of self-promotion.

Readings

Deitel and Deitel Fifth Edition, Chapter ?.?, ?.?, ?.?