Wednesday, November 8, 2006 Monday, November 13, 2006 Wednesday, November 15, 2006

Searching and Sorting

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.
• 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.
• Bubble Sort pseudocode:
•     int functionBubbleSort(datatype array[], int size)
•     {
•         int indexforhighest;
•         int indexforswap;
•        
•         for (indexforhighest = size - 1; indexforhighest > 0; indexforhighest--)
•         {
•             for (indexforswap = 0; indexforswap < indexforhighest; indexforswap++)
•             {
•                 if (array[indexforswap] > array[indexforswap + 1])
•                 {
•                     // swap array[indexforswap] with array[indexforswap + 1]
•                 }
•             }
•         }
•     }
• 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.
• Selection Sort pseudocode:
•     int functionSelectionSort(datatype array[], int size)
•     {
•         int indextoputlowest;
•         int indextocheck;
•         int indexoflowest;
•        
•         for (indextoputlowest = 0; indextoputlowest < size - 1; indextoputlowest++)
•         {
•             indexoflowest = indextoputlowest;
•             for(indextocheck = indextoputlowest + 1; indextocheck < size; indextocheck++)
•             {
•                 if (array[indexoflowest] > array[indextocheck])
•                 {
•                     indexoflowest = indextocheck;
•                 }
•             }
•             // swap array[indextoputlowest] with array[indexoflowest]
•         }
•     }
•  
• 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..
• Two O(n lg(n)) sorts are the Quick Sort and the Shell Sort.  The algorithms are beyond the scope of this course.
• These sorts are an order of magnitude faster than the O(n²)  sorts.  If you have a large number of data to sort, you would definitely want to use an O(n lg(n)) sort.
•  
• Binary Searches
• If an array is already sorted, searching the array can be a lot faster using a Binary Search instead of a simple for loop to check each member of the array.
• A Binary Search simply checks the middle of the sorted array.  If the value being searched for is less than the value at the half way point, then the value must be in the lower half.  If the value being searched for is greater than the value at the half way point, then the value must be in the top half.  You then just repeat the process with the proper half, finding the quarter the value must be in, then the eighth, the sixteenth, and so on.  When the size of the remaining part of the array to search is only one value, then it either must be the value looked for.  If not, then the value looked for is not in the array.
• Binary Search pseudocode:
•     int functionBinarySearch(datatype array[], int size)
•     {
•         int searchsize = size;
•         int baseindex = 0;
•         int halfwayindex = size / 2; // integer division
•        
•         while(searchsize > 1)
•         {
•             if (valuelookedfor == array[halfwayindex])
•             {
•                 return halfwayindex;
•             }
•             else if (valuelookedfor < array[halfwayindex])
•             {
•                 searchsize /= 2;
•             else if (valuelookedfor < array[halfwayindex])
•             {
•                 searchsize /= 2;
•                 // baseindex is left unchanged
•                 halfwayindex = baseindex + searchsize / 2;
•             }
•                 halfwayindex = baseindex + searchsize / 2;
•             }
•             else // valuelookedfor > array[halfwayindex]
•             {
•                 searchsize /= 2;
•                 baseindex = halfwayindex;
•                 halfwayindex = baseindex + searchsize / 2;
•             }
•         }
•         return VALUE_NOT_FOUND;
•     }

Readings