tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (2nd AP edition): Chapter 14 - Maria Litvin, Gary Litvin

Chapter 14 - Searching and sorting. This chapter is a survey of the basic searching and sorting algorithms including the four standard sorting algorithms. This chapter’s objectives are to: Learn about the three ways to compare objects in Java, learn the following algorithms. | Searching and Sorting 14ACEHRPT Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 14- This chapter is a survey of the basic searching and sorting algorithms including the four standard sorting algorithms. Objectives: Learn about the three ways to compare objects in Java Learn the following algorithms Sequential and Binary Search Selection Sort and Insertion Sort Mergesort and Quicksort Learn about the and classes 14- An unstated objective is to get a feel for the big-O of different algorithms without introducing this concept formally. Comparing Objects in Java boolean result = (obj2); int diff = (obj2); int diff = (obj1, obj2); 14- Comparators and compare are not in the AP subset. (obj2) The boolean method equals comes from the . | Searching and Sorting 14ACEHRPT Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 14- This chapter is a survey of the basic searching and sorting algorithms including the four standard sorting algorithms. Objectives: Learn about the three ways to compare objects in Java Learn the following algorithms Sequential and Binary Search Selection Sort and Insertion Sort Mergesort and Quicksort Learn about the and classes 14- An unstated objective is to get a feel for the big-O of different algorithms without introducing this concept formally. Comparing Objects in Java boolean result = (obj2); int diff = (obj2); int diff = (obj1, obj2); 14- Comparators and compare are not in the AP subset. (obj2) The boolean method equals comes from the class Object: Object’s equals is not very useful: compares addresses of objects Programmers often override equals in their classes public boolean equals(Object other) { . } 14- Note that the type of parameter is Object because this method is defined in the class Object. (obj2) (cont’d) public class Pet { private String name; . public boolean equals (Object other) { if (other != null) return (((Pet)other).name); else return false; } } Or: if (other instanceof Pet) instanceof is a boolean operator in Java 14- The version with (other != null) throws a ClassCastException when other is not a Pet; the version with instanceof simply returns false. (obj2) (cont’d) equals is called polymorphically from library methods, such as ArrayList’s contains or indexOf that is why we have to properly override Object’s equals. The equals method is properly defined in String, Integer, Double, etc. 14- String also has equalsIgnoreCase. (obj2) .