Ch07File.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Notice that the function call is written Sum(score), not Sum(score()), and that the parameter declaration is written ByVal s() As Integer, not ByVal s As Integer. * An efficient alternative to the sequential search is the binary search, which is considered in Section 7.4. * * * * * * * * * * * * Chapter 7 - VB 2008 by Schneider * Shell Sort Algorithm Begin with a gap of g = Int(n/2) Compare items 0 and g, 1 and 1 + g, . . ., n - g and n. Swap any pairs that are out of order. Repeat Step 2 until no swaps are made for gap g. Halve the value of g. Repeat Steps 2, 3, and 4 until the value of g is 0. Chapter 7 - VB 2008 by Schneider * Searching Sequential search starts at the beginning of a list and keeps looking one by one until the item is found or the end of the list is reached. For a sequential search, the list need not be sorted. Chapter 7 - VB 2008 by Schneider * Binary Search Usually more efficient than sequential search List must be sorted Chapter 7 - VB 2008 by Schneider * Binary Search: Algorithm Given: an array in ascending order and a sought-after value, quarry, that may be in the array. Repeatedly halve the range of indices where quarry might be found. Halving routine looks at the middle value of the current range and compares it to quarry with =, , and . If middle value = quarry, then search is over. If middle value quarry, then we can limit our search to the half of the range below the middle value. If middle value quarry, then we can limit our search to the half of the range above the middle value. Chapter 7 - VB 2008 by Schneider * Binary Search: Variables first – lower limit of range of values to search last – upper limit of range of values to search middle = Int((first + last) / 2) a() – ordered array to be searched foundFlag – True when quarry is found Note: If quarry is not in the array, eventually last will be greater than first. Note: Initially first