Kĩ thuật lập trình - Searching and sorting

Searching and Sorting 14ACEHRPT Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn about the three ways to compare objects in JavaLearn the following algorithmsSequential and Binary SearchSelection Sort and Insertion SortMergesort and QuicksortLearn about the java.util.Arrays and java.util.Collections classes2Comparing Objects in Javaboolean result = obj1.equals(obj2);int diff = obj1.compareTo(obj2);int diff = c.compare(obj1, obj2);3obj1.equals(obj2)The boolean method equals comes from the class Object:Object’s equals is not very useful: compares addresses of objectsProgrammers often override equals in their classespublic boolean equals(Object other) { ... }4obj1.equals(obj2) (cont’d)public class Pet{ private String name; ... public boolean equals (Object other) { if (other != null) return name.equals(((Pet)other).name); else return false; }}Or: if (other instanceof Pet)instanceof is a boolean operator in Java5obj1.equals(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.6obj1.compareTo(obj2)compareTo is an abstract method defined in the java.util.Comparable interface:Returns a positive integer if obj1 is “greater than” obj2, a negative integer if obj1 is “less than” obj2, zero if they are “equal.”public int compareTo (T other);Sort of like obj1 - obj2T is the type parameter7obj1.compareTo(obj2) (cont’d)public class Pet implements Comparable{ private String name; ... public int compareTo(Pet other) { return name.compareTo(other.name); } public boolean equals(Object other) { return other instanceof Pet && compareTo((Pet)other) == 0; }}equals is not required by Comparable, but it is a good idea to provide it and make it agree with compareTo8obj1.compareTo(obj2) (cont’d)compareTo is called polymorphically from library methods, such as Arrays.binarySearch(Object[ ] arr).Objects of classes that implement Comparable are called “comparable” (pronounced com-'parable).Strings, Integers, Doubles are comparable.9obj1.compareTo(obj2) (cont’d)«interface»ComparableStringcompareTo is based on lexicographical order«interface»Comparable«interface»ComparableIntegerDoublecompareTo is based on numerical values10compare(obj1, obj2)compare is an abstract method defined in the java.util.Comparator interface:Returns a positive integer if obj1 is “greater than” obj2, a negative integer if obj1 is “less than” obj2, zero if they are “equal.”public int compare (T obj1, T obj2);Sort of like obj1 - obj2T is the type parameter11compare (obj1, obj2) (cont’d)public class PetComparatorByName implements Comparator{ ... public int compare (Pet pet1, Pet pet2) { return pet1.getName(). compareTo(pet2.getName()); }}12compare(obj1, obj2) (cont’d)A programmer can define different comparators to be used in different situations.compare is called from library methods, such as Arrays.sort(T [ ] arr, Comparator c) (or from your own methods) that take a comparator object as a parameter.13Sequential SearchScans the list comparing the target value to each element.Amy5Ben3Cal2Dan0Eve6Fay1Guy4Amy?Amy?Amy?Amy?Amy?Amy!14Sequential Search (cont’d)public int sequentialSearch(Object [ ] arr, Object value){ for (int i = 0; i arr[middle]) return binarySearch (arr, value, middle + 1, right);}19Binary Search (cont’d)Iterative implementation:public int binarySearch (int [ ] arr, int value, int left, int right){ while (left arr[middle] ) left = middle + 1; } return -1; // Not found}20Binary Search (cont’d)A “divide and conquer” algorithm.Works very fast: only 20 comparisons are needed for an array of 1,000,000 elements; (30 comparisons can handle 1,000,000,000 elements; etc.).We say that this is an O(log n) algorithm.21SortingTo sort means to rearrange the elements of a list in ascending or descending order.Examples of sorting applications:a directory of files sorted by name or datebank checks sorted by account #addresses in a mailing list sorted by zip codehits found by a search engine sorted by relevancecredit card transactions sorted by date22Sorting (cont’d)The algorithms discussed here are based on “honest” comparison of values stored in an array. No tricks.How fast can we sort an array of n elements?If we compare each element to each other we need n(n-1) / 2 comparisons (that is, n2 by the “order of magnitude.”)Faster “divide and conquer” sorting algorithms need approximately n·log2 n comparisons (much better).23Sorting (cont’d)nTimen2n log2 n n 10 100 1000 n2 100 10,000 1,000,000n log2 n 35 700 10,00024Selection Sort1. Select the max among the first n elements:2. Swap it with the n-th element :3. Decrement n by 1 and repeat from Step 1 (while n > 1)11385213n11385213n11385213n25Selection Sort (cont’d)Iterative implementation:public void selectionSort (double [ ] arr, int n){ while (n > 1) { int maxPos = 0; for (int k = 1; k arr [maxPos] ) maxPos = k; double temp = arr [maxPos]; arr [maxPos] = arr [n-1]; arr [n-1] = temp; n--; }}swap a[maxPos] and a[n-1]26Selection Sort (cont’d)The total number of comparisons is always (n-1) + (n-2) + ... + 1 = n(n-1) / 2No average, best, or worst case — always the same.An O(n2) algorithm.27Insertion Sort1. k = 1; keep the first k elements in order.2. Take the (k+1)-th element and insert among the first k in the right place.3. Increment k by 1; repeat from Step 2 (while k 0 && arr [i-1] > temp) { arr [i] = arr [i - 1]; i --; } arr [i] = temp; } }shift to the right29Insertion Sort (cont’d)The average number of comparisons is roughly half of the number in Selection Sort.The best case is when the array is already sorted: takes only (n-1) comparisons.The worst case is n(n-1) / 2 when the array is sorted in reverse order.On average, an O(n2) algorithm.30Mergesort1. Split the array into two roughly equal “halves.”2. Sort (recursively) each half using... Mergesort.3. Merge the two sorted halves together.546327117652437654132The smaller value goes first31231Mergesort (cont’d)public void mergesort (double[ ] arr, int from, int to){ if (from arr [middle + 1]) { copy (arr, from, to, temp) ; merge (temp, from, middle, to, arr); }}double[ ] temp is initialized outside the mergesort methodOptional shortcut: “if not yet sorted”...Base case32Mergesort (cont’d)Takes roughly n·log2 n comparisons.Without the shortcut, there is no best or worst case.With the optional shortcut, the best case is when the array is already sorted: takes only (n-1) comparisons.An O(n log n) algorithm.33Quicksort1. Pick one element, called “pivot”2. Partition the array, so that all the elements to the left of pivot are  pivot; all the elements to the right of pivot are  pivot.3. Sort recursively the left and the right segments using... Quicksort.5436271456327134Quicksort (cont’d)Takes roughly n·log2 n comparisons.May get slow if pivot consistently fails to split the array into approximately equal halves.An O(n log n) algorithm.35The Benchmarks programEnter the array sizeRunning time in millisecondsChoose the sorting algorithm36java.util.RandomBenchmarks uses the java.util.Random class — a more controlled way to generate random numbers.Constructors:If we set the same seed, we get the same “random” sequence.Random generator1 = new Random();Random generator2 = new Random(seed);long seed;the seed is different each time37java.util.Random (cont’d)Methods: int k = generator.nextInt (n);double x = generator.nextDouble ();0  k < n0  x < 138java.util.ArraysProvides static methods for dealing with arrays.Works for arrays of numbers, Strings, and Objects.Methods: int pos = Arrays.binarySearch (arr, target);Arrays.sort (arr);Arrays.fill (arr, value); // fills arr with a given valueString str = Arrays.toString(arr);Arrays.asList(arr);Returns a representation of arr as a fixed-length list39java.util.CollectionsProvides static methods for dealing with ArrayLists and other Java collections.Works for arrays of numbers, Strings, and Objects.Methods: int pos = Collections.binarySearch (list, target);Collections.sort (list);Collections.shuffle (list);40Review:What is the type of the parameter in the equals method?How many methods are listed in the Comparable interface?What is a comparator?How many comparisons are needed in the worst case to find the target value among 15 values using Sequential Search? Using Binary Search?41Review (cont’d):Describe briefly the main idea of Selection Sort.Describe briefly the main idea of Insertion Sort.Is it easier to implement Mergesort recursively or iteratively?What is the average number of comparisons in Mergesort?Name a few methods of the java.util.Arrays class.42