tailieunhanh - Lecture An introduction to Object-Oriented Programming with Java - Chapter 11: Sorting and searching

In this chapter, we will present a better searching algorithm called binary search. To apply binary search, an array must be sorted. Sorting is a technique to arrange elements in some order, and it is one of the fundamental operations we study in computer science. | Chapter 11 Sorting and Searching Chapter 11 Objectives After you have read and studied this chapter, you should be able to Perform 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 to Describe 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. Searching Searching 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 Successful and unsuccessful searches. ©TheMcGraw-Hill Companies, Inc. Permission required for reproduction or display. Searching We will examine two searching algorithms: Linear search Binary search A 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. Searching In 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 . | Chapter 11 Sorting and Searching Chapter 11 Objectives After you have read and studied this chapter, you should be able to Perform 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 to Describe 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. Searching Searching an array or other data structure has two possible outcomes: Successful search