tailieunhanh - Lecture An introduction to object-oriented programming with Java: Chapter 11 - C. Thomas Wu
In chapter 11, we cover searching and sorting. 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, describe the heapsort algorithm and show how its performance is superior to the other two algorithms, apply basic sorting algorithms to sort an array of objects. | ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 11 - Chapter 11 Sorting and Searching Animated Version Introduction to OOP with Java 4th Ed, C. Thomas Wu © The McGraw-Hill Companies, Inc. ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 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. Describe the heapsort algorithm and show how its performance is superior to the other two algorithms. Apply basic sorting algorithms to sort an array of objects. Intro to OOP with Java, C. Thomas Wu ©The McGraw-Hill Companies, Inc. ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 11 - Searching When we maintain a collection of data, one of the operations we need is a search routine to locate desired data quickly. Here’s the problem statement: Given a value X, return the index of X in the array, if such X exists. Otherwise, return NOT_FOUND (-1). We assume there are no duplicate entries in the array. We will count the number of comparisons the algorithms make to analyze their performance. The ideal searching algorithm will make the least possible number of comparisons to locate the desired data. Two separate performance analyses are normally done, one for successful search and another for unsuccessful search. Intro to OOP with Java, C. Thomas Wu ©The McGraw-Hill Companies, Inc. ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 11 - Search Result number 23 17 5 90 12 44 38 0 1 2 3 4 5 6 7 8 84 77 Unsuccessful Search: Successful Search: NOT_FOUND search( 45 ) search( 12 ) 4 Intro to OOP with Java, C. Thomas Wu ©The McGraw-Hill Companies, Inc. ©The McGraw-Hill Companies, . | ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 11 - Chapter 11 Sorting and Searching Animated Version Introduction to OOP with Java 4th Ed, C. Thomas Wu © The McGraw-Hill Companies, Inc. ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 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. Describe the heapsort algorithm and show how its performance is superior to the other two algorithms. Apply basic sorting algorithms to sort an array of objects. Intro to OOP with Java, C. Thomas Wu ©The McGraw-Hill Companies, Inc. ©The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Chapter 11 - Searching When we maintain a collection of data, one of
đang nạp các trang xem trước
