Popular in Course
verified elite notetaker
Popular in Department
This 6 page Reader was uploaded by Eli Fine on Monday August 25, 2014. The Reader belongs to a course at a university taught by a professor in Fall. Since its upload, it has received 281 views.
Reviews for 328479845Chapter13CS.pdf
So much better than office hours. Needed something I could understand, and I got it. Will be turning back to StudySoup in the future
-Lavinia Hegmann III
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 08/25/14
Chapter 13 amp 18 131 Prologue 2 Searching algorithms Sequential Search Binary Search Common Sorting algorithms Selection Sort Insertion Sort Mergesort Quicksort 132 equgls compareTo and compz Another way to think of these methods are as extensions of things Such as nameequals or namecompareTo Java offer 3 ways for comparing objects public Boolean equasObject other The boolean method equals compares this object to other for equality public int compareTo Tother The int mthod compareTo compares this object to another object of the same type and returns an integer that indicates whether this is greater than equal to or less than other public int compareTobj1 Tobj2 the int method compare compares two objects of the same type and returns an integer that indicates which of the two objects is greater than the other T is the name of your class 1 eguals The equals method public boolean equasobject other This is a method of the class Object It compares the addresses of this and other and returns true if they are the same or false otherwise nsert 131 example here In order to override Object s equals method in your class the signature of your equals method must be exactly the same as the signature of equals in Object In particular the declared type of the parameter other must be Object Note that overriding the Object s equal method does not change the meaning of the operator for the objects of your class it still compares addresses of objects 2 compareTo The compareTo method is an abstract method defined in the javautiComparabelt Tgt interface Once again the syntax is public int compareToT other T is the name of your class Ex public class Country implements comparabeltCountrygt public int compareToCountry other return namecompareToothergetname compareTo returns an int a positive value indicates that this is greater than other a zero indicates that this is less than other So xcompareToy is sort of like xy Note that compareTo takes a parameter of your class type not Object String Integer Double and several other library classes implement Comparable If you do define a compareTo method in your class don t forget to state it in the header of your class example 7 implements ComparabeltYourCassgt If your class implements Comparable then it is a good idea to define the equals method and to make compareTo and equals agree with each other so that xequasy returns true if and only if xcompareToy returns 0 Countries is now comparable and can also be sorted through Arrayssort 3 compare also known as a comparator it is an object that compares two objects of your class public int compareT objl T obj2 lf compare returns a positive integer obj1 is considered greater than obj2 if the returned value is 0 they are considered equal if the returned value is negative obj1 is considered less than obj2 So compareobh1 obj2 is sort of like obj1 obj2 The purpose of comparators is to be passed as parameters to constructors and methods of certain library classes or your own classes 133 Seguential and Binary Search Sequential Search Checks the value of each consecutive element one by one until we find the target element or finish scanning the whole array Example String words ltsome wordsgt String target lt a wordgt for int k 0 k ltwordsength k if targetequaswordsk return k Binary Search A binary search can be used if the elements of the array are arranged in ascending or descending order aka sorted A binary search in an array of 3 elements requires at most 2 comparisons to find the target value or establish that it is not in the array In an array of 7 elements it requires at most 3 comparisons Of 15 elements 4 comparisons And so on An array of 2 1 or fewer elements requires at most n comparisons Example of Binary Search ltinsert 134 figure heregt Given int a 8 13 21 34 55 89 a0 8 a1 13 a2 21 a3 34 a4 55 a5 89 target 34 Initially left 0 right aength 1 5 First iteration middle 052 2 amidde a2 21 target gt amidde 34 gt 21 Set left middle 1 3 right remains 5 Second Iteration middle 352 4 amidde a4 55 target lt amidde 34 lt 55 Set right middle 1 3 left remains 3 Third iteration middle 332 3 amidde a3 34 target amidde 34 34 return 3 135 Selection Sort 1 Initialize a variable n to the size of the array 2 Find the largest among the first n elements 3 Make it swap places with the nth element 4 Decrement n by 1 5 Repeat steps 2 4 while n gt 2 ltinsert 135 exampegt The SeectionSort class in Figure 135 implements this algorithm for an array of the type double A similar procdure will sort the array in descending order instead of finding the largest element on each iteration We can simply find the smallest element among the first n 136 Insertion Sort The purpose of the Insertion Sort algorithm is to keep the beginning part of the array sorted and insert each next element into the correct place in it Insertion Sort 1 Initialize a variable n to 1 keep the first n elements sorted 2 Save the next element and find the place to insert it among the first nso that the order is preserved 3 Shift the elements as necessary to the right and insert the saved one in the created vacant slot 4 Increment n by 1 5 Repeat Steps 2 4 while n lt array length The nsertionSort class in Figure 136 implements this algorithm for an array of doube s ltinsert figure 136gt 137 Mergesort Mergesort 1 If the array has only one element do nothing 2 Optional If the array has two elements swap them if necessary 3 Split the array into two approximately equal halves 4 Sort the first half and the second half 5 Merge both halves into one sorted array Recursive methods must recognize two possibilities a base case and a recursive case base case no recursive calls are needed and the base case occurs when the array has or1y one or two elements recursive case The recursive case must reduce the task to similar BUT smaller tasks ltnsert 137 figure heregt Figure 137 shows a Mergesort class that can sort an array of doubles The sort method calls a recursive helper method that sorts a particular segment of the array The merge method is not recursive To understand how it works imagine two piles of cards each sorted in ascending order and placed face up on the table We want to merge them into the third sorted pike On each step we take the smaller of the two exposed cards and place it face down on top of the destination pile When one of the original piles is gone we take all the remaining cards in the other one and place them face down on top of the destination pile We end up with the destination pile sorted in ascending Mergesort is an On log n algorithm much beter than the 0nquot2 performance of Selection Sort and Insertion Sort 138 Quicksort Quicksort is another On log n sorting algorithm The idea Quicksort is to pick one element called the pivot then rearrange the elements of the array in such a way that all the elements to the left of the pivot are smaller than or equal to it and all the elements to the right of pivot are greater than or equal to it The pivot element can be chosen arbitrarily among the elements of the array This procedure is called partitioning After partitioning Quicksort is applied recursively to the leftofpivot part and to the right ofpivot part which results in a sorted array ltinsert figure 139gt Figure 138 shows the partitioning algorithm You process from both ends of the array toward the meeting point comparing the elements with the pivot ltinsert figure 138gt 1310 iavautiArrays and iavautiCollections javauti package has a class Arrays and a class Collections with methods that implement Binary search and sorting You need to import javautiArrays or javautiCoections in order to use their methods ALL of Arrays s and Coections s methods are static and you cannot create objects of these classes Arrays s binarySearch method Syntax int pos ArraysbinarySearcha target Arrays class has overloaded versios of binarySearch for arrays of char s int s and other primitive data types