Kĩ thuật lập trình - Chương 16: Searching and sorting

16Searching and Sorting 1 With sobs and tears he sorted outThose of the largest size ...Lewis CarrollAttempt the end, and never stand to doubt;Nothing’s so hard, but search will find it out. Robert Herrick‘Tis in my memory lock’d,And you yourself shall keep the key of it. William ShakespeareIt is an immutable law in business that words are words, explanations are explanations, promises are promises — but only performance is reality. Harold S. Green2OBJECTIVESIn this chapter you will learn:To search for a given value in an array using linear search and binary search.To sort arrays using the iterative selection and insertion sort algorithms.To sort arrays using the recursive merge sort algorithm.To determine the efficiency of searching and sorting algorithms.To use loop invariants to help ensure the correctness of your programs.316.1    Introduction 16.2    Searching Algorithms 16.2.1   Linear Search 16.2.2   Binary Search 16.3    Sorting Algorithms 16.3.1   Selection Sort 16.3.2   Insertion Sort 16.3.3   Merge Sort 16.4    Invariants 16.5    Wrap-up 416.1 IntroductionSearchingDetermining whether a search key is present in dataSortingPlaces data in order based on one or more sort keys5Fig. 16.1 | Searching and sorting algorithms in this text. 616.2 Searching AlgorithmsExamples of searchingLooking up a phone numberAccessing a Web siteChecking a word in the dictionary716.2.1 Linear SearchLinear searchSearches each element sequentiallyIf search key is not presentTests each elementWhen algorithm reaches end of array, informs user search key is not presentIf search key is presentTest each element until it finds a match89Iterate through arrayTest each element sequentiallyReturn index containing search key101112Efficiency of Linear Search Big O NotationIndicates the worst-case run time for an algorithmIn other words, how hard an algorithm has to work to solve a problemConstant run timeO(1)Does not grow as the size of the array increasesLinear run timeO(n)Grows proportional to the size of the array13Efficiency of Linear Search Big O NotationConstant run timeO(1)Does not grow as the size of the array increasesLinear run timeO(n)Grows proportional to the size of the arrayQuadratic run timeO(n2)Grows proportional to the square of the size of the array14Efficiency of Linear Search Linear search algorithmO(n)Worst case: algorithm checks every element before being able to determine if the search key is not presentGrows proportional to the size of the array15Performance Tip 16.1Sometimes the simplest algorithms perform poorly. Their virtue is that they are easy to program, test and debug. Sometimes more complex algorithms are required to realize maximum performance. 1616.2.2 Binary Search Binary searchMore efficient than linear searchRequires elements to be sortedTests the middle element in an arrayIf it is the search key, algorithm returnsOtherwise, if the search key is smaller, eliminates larger half of arrayIf the search key is larger, eliminates smaller half of arrayEach iteration eliminates half of the remaining elements1718Store high, low and middle of remaining array to searchLoop until key is found or no elements left to searchIf search element is the middle elementReturn middle elementIf search element is less than middle elementEliminate higher halfElse, eliminate lower half19Update middle of arrayReturn location of element20212223Efficiency of Binary SearchBinary searchEach comparison halves the size of the remaining arrayResults in O(log n)Called logarithmic run time2416.3 Sorting AlgorithmsSorting dataPlacing data into some particular orderA bank sorts checks by account numberTelephone companies sort accounts by nameEnd result is always the same – a sorted arrayChoice of algorithm affects how you achieve the result and, most importantly, how fast you achieve the result2516.3.1 Selection SortSelection sortSimple, but inefficient sorting algorithmFirst iteration selects smallest element in array and swaps it with the first elementEach iteration selects the smallest remaining unsorted element and swaps it with the next element at the front of the arrayAfter i iterations, the smallest i elements will be sorted in the first i elements of the array26Variable to store index of smallest elementLoop length – 1 times27Loop over remaining elementsLocate smallest remaining elementSwap smallest element with first unsorted element28293031Efficiency of Selection SortSelection sortOuter for loop iterates over n – 1 elementsInner for loop iterates over remaining elements in the arrayResults in O(n2)3216.3.2 Insertion SortInsertion sortAnother simple, but inefficient sorting algorithmFirst pass takes the second element and inserts it into the correct order with the first elementEach iteration takes the next element in the array and inserts it into the sorted elements at the beginning of the arrayAfter i iterations, the first i elements of the array are in sorted order3334Declare variable to store element to be insertedIterate over length – 1 elementsStore value to insertSearch for location to place inserted elementMove one element to the rightDecrement location to insert elementInsert element into sorted place3536373839Efficiency of Insertion SortInsertion sortOuter for loop iterates over n – 1 elementsInner while loop iterates over preceding elements of arrayResults in O(n2)4016.3.3 Merge SortMerge sortMore efficient sorting algorithm, but also more complexSplits array into two approximately equal sized subarrays, sorts each subarray, then merges the subarraysThe following implementation is recursiveBase case is a one-element array which cannot be unsortedRecursion step splits an array into two pieces, sorts each piece, then merges the sorted pieces41Call recursive helper method42Test for base caseCompute middle of arrayCompute element one spot to right of middleRecursively sort first half of arrayRecursively sort second half of arrayMerge the two sorted subarrays43Index of element in left arrayIndex of element in right arrayIndex to place element in combined arrayArray to hold sorted elementsLoop until reach end of either arrayDetermine smaller of two elementsPlace smaller element in combined array44If left array is emptyFill with elements of right arrayIf right array is emptyFill with elements of left arrayCopy values back to original array454647484950Efficiency of Merge SortMerge sortFar more efficient that selection sort or insertion sortLast merge requires n – 1 comparisons to merge entire arrayEach lower level has twice as many calls to method merge, with each call operating on an array half the size which results in O(n) total comparisonsThere will be O(log n) levelsResults in O(n log n)51Fig. 16.12 | Searching and sorting algorithms with Big O values. 52Fig. 16.13 | Number of comparisons for common Big O notations. 5316.4 InvariantsInvariantIs an assertion that is true before and after a portion of your code executesMost common type is a loop invariant5416.4 InvariantsLoop invariant remains true:Before the execution of the loopAfter every iteration of the loop bodyWhen the loop terminates5516.4 InvariantsFour steps to developing a loop from a loop invariantSet initial values for any loop control variablesDetermine the condition that causes the loop to terminateModify the control variable so the loop progresses toward terminationCheck that the invariant remains true at the end of each iteration56