Bài giảng Chapter 11: Sorting and Searching

Chapter 11Sorting and Searching©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 11 ObjectivesAfter you have read and studied this chapter, you should be able toPerform linear and binary search algorithms on small arrays.Determine whether a linear or binary search is more effective for a given situation.Perform selection and bubble sort algorithms.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 11 Objectives, cont.After you have read and studied this chapter, you should be able toDescribe the heapsort algorithm and show how its performance is superior to that of the other two algorithms.Apply basic sorting algorithms to sort an array of objects, using the Comparator interface.Define the interface to specify common behavior and provide different versions of classes that implement the interface.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.1 SearchingSearching an array or other data structure has two possible outcomes:Successful search (value found)Unsuccessful search (value not found)It is possible for one searching algorithm to perform very well for successful searches, and very poorly for unsuccessful searches.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Figure 11.1Successful and unsuccessful searches.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.1 SearchingWe will examine two searching algorithms:Linear searchBinary searchA linear search searches the array from the first index position to the last in a linear progression. This search is also known as a sequential search. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.1 SearchingIn a linear search, if the number of entries in the array is N, there will be N comparisons for an unsuccessful search. For a successful search, there will be a minimum of 1 and a maximum of N comparisons. On average, there will be N/2 comparisons.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.1 SearchingBelow is a linear search algorithm.public int linearSearch (int[] number, int searchValue) { int loc = 0; while ( loc searchValue high = mid - 1; } mid = (low + high) / 2; } if ( low > high) { mid = NOT_FOUND; } return mid; }}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.3How the unsuccessful search is terminated in the binary search routine.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingSorting is a technique to arrange elements in some order.We will examine three sorting algorithms:Selection sortBubble sortHeapsort©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingA natural sorting algorithm for a human looks like this:Find the smallest integer in the list.Cross out the number and copy it to a new sorted list.Repeat steps 1 and 2 until all numbers in the list are crossed out.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.4Human sorting algorithm after three numbers are moved to the sorted list.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingSelection sort is somewhat like the human approach. It finds the smallest number in a given list and moves it to the correct position in the list.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingSelection sort is comprised of sorting passes. We locate the smallest element in the array and set the index min to point to this element.We then exchange number[start] and number[min]. After the first pass, the smallest element is moved to the correct position.We increase the value of start by 1 and execute the second pass.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.5Effect of executing the first pass in the selection sort.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingWe start the first pass with start = 0 and end the last pass with start = N-2. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.6Eight passes to sort the sample array of nine elements.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingIn selection sort, we make one data exchange per pass. In bubble sort, we make pairwise comparisons and exchange the pair if they are out of order.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.7Effect of executing the first pass in the bubble sort.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingIn the worst case, bubble sort will make N-1 passes, so its worst-case performance is the same as that of selection sort.Bubble sort exhibits two properties:After one pass through the array, the largest element will be at the end of the array.During one pass, if no pair of consecutive entries is out of order, then the array is sorted.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.2 SortingOn average, we expect the bubble sort to finish sorting sooner than selection sort because there are more data movements for the same number of comparisons. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortThe heapsort algorithm is generally much more efficient than either the bubble sort or the selection sort.The heapsort algorithm uses a special data structure called a heap.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortA heap consists of nodes, which contain data values, and edges, which link the nodes.The topmost node is called the root node of a heap.Nodes in a heap are indexed 0, 1, 2, and so on in top-to-bottom, left-to-right order.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.8A sample heap that includes nine nodes.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortA node in a heap has zero, one, or two children.The children of a node are distinguished as the node’s left or right children.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortA heap must satisfy two constraints:Structural constraint: Nodes in a heap with N nodes must occupy the positions numbered 0, 1,...,N-1. Value relationship constraint: A value stored in a node must be larger than the maximum of the values stored in its left and right children.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.9Sample heaps and nonheaps that violate the structural constraint.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.10Sample heaps and nonheaps that violate the value relationship constraint. Violations are indicated by blue ellipses.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortHeapsort is carried out in two phases:Construction phase: Construct a heap given N elements.Extraction phase: Pull out the value in the root successively, creating a new heap with one less element after each extraction step.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortIf every node in the heap satisfies the value relationship constraint, then the value in the root node is the largest value in the heap. We then remove that value, and reconstruct a heap by moving the last element to the root position.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortWe examine each node to confirm that both the structural and value relationship constraints are met. If the value relationship constraint is not met, we swap values until the relationship is satisfied.This swapping process is called a rebuild step.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.11One rebuild step after the value 90 is pulled out of the heap. The net result of a single rebuild step is a new heap that contains one fewer element.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortIn a heap of N elements, we can sort the N elements by performing the rebuild steps N-1 times.The array for the sorted list is filled from the end.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.12Eight rebuild steps to sort a heap with nine elements.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortWe will examine the construction phase using the following unsorted numbers:23, 17, 5, 90, 12, 44, 38, 84, 77Assigning the numbers to a heap structure in ascending index order produces a heap that violates the value relationship constraint. The construction phase eliminates these violations.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.13A heap structure with given numbers assigned in ascending index order.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortThe rebuild step is critical for constructing a heap. We build a heap in bottom-up fashion, starting small, and gradually building larger until all elements are contained in the heap.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.14Sequence of rebuild steps applied in the construction phase. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortThe array is one of the most effective data structures we can use to implement the heapsort in Java.With an array implementation, we can easily locate a given node’s left and right children. A node with index I has its left child at index 2I + 1 and its right child at index 2I + 2.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.15A sample heap and the corresponding array implementation.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 Heapsort/*Chapter 11 Sample Program: Heap algorithm.File: Heap.java*//** * Basic class for implementing the heapsort algorithm. * This class works only for integers.*/public class Heap { private int[ ] heap; private int[ ] sortedList; public Heap( ) { }©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 Heapsort//-------------------------------------------------// Public Methods://------------------------------------------------public void setData( int[ ] data ) { heap = new int[ data.length ]; sortedList = new int[ data.length ]; for (int i = 0; i = 0; i--) { current = i; done = false; while ( !done ) { if ( 2*current+1 > heap.length-1 ) { //current node has no children, so stop done = true; } else { //current node has at least one child, //get the index of larger child maxChildIndex = maxChild( current, heap.length-1 ); ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 Heapsort if ( heap[current] = 0; size--) { //remove the root node data sortedList[size] = heap[ 0 ]; //move the last node to the root heap[ 0 ] = heap[size]; //rebuild current = 0; done = false; while ( !done ) { if ( 2*current+1 > size ) { //current node has no children, so stop done = true; } else { //current node has at least one child, //get the index of larger child maxChildIndex = maxChild( current, size );©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 Heapsort if ( heap[current] < heap[maxChildIndex] ) { swap( current, maxChildIndex ); current = maxChildIndex; } else { //value relationship constraint //is satisfied, so stop done = true; } } } assert isValidHeap(heap, 0, size): "Error: Extraction phase is not working ” + “correctly"; //testPrint( size ); //TEMP }} ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 Heapsortprivate int maxChild( int location, int end ) { int result, leftChildIndex, rightChildIndex; rightChildIndex = 2*location + 2; leftChildIndex = 2*location + 1; //Precondition: node at 'location' has at least //one child assert heap[leftChildIndex] <= end: "Error: node at position " + location + "has no children."; if ( rightChildIndex <= end && heap[leftChildIndex] < heap[rightChildIndex]) { result = rightChildIndex; } else { result = leftChildIndex; } return result;} ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 Heapsortprivate void swap ( int loc1, int loc2 ) { int temp; temp = heap[loc1]; heap[loc1] = heap[loc2]; heap[loc2] = temp; } private void testPrint( int limit ) { for (int i = 0; i < limit; i++) { System.out.print(" " + heap[i]); } System.out.println( " " ); }}©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortBubble sort and selection sort perform roughly N2 comparisons for sorting N elements. Heapsort performs roughly 1.5N log2 N comparisons for sorting N elements.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.11.3 HeapsortThe level of a node in a heap refers to the number of nodes in the path from the root to the node in question.The depth of a heap is defined to be the largest level of the nodes in the heap.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.Fig. 11.16A sample heap with depth = 4, which is defined to be the largest level of all nodes in a heap.©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display.