Comparison of Objects (The equals method)
public boolean equals(Object other) is a method from the Object class. It is an important method because it is inherited by all classes that we create and tells how to determine if two objects are equal. However, the equals method in the Object class is not very helpful. It compares the addresses of two objects to determine if they are the same object, not whether their contents are the same.
Because of this, we override the equals method in our classes and specify how we want to test for equality of these objects.
Example from Rectangle class:
public boolean equals(Object other)
{
Rectangle temp = new Rectangle();
temp = (Rectangle)other;
return getArea() == temp.getArea();
}
Notes: If we had created a method: public boolean equals(Rectangle other) it would work correctly some of the time but the problem is that it does not override the equals method from the Object class.
- the contains and indexOf methods for ArrayList is an example of a method that implicitly uses the equals method for Object.
- We want to override equals so we must cast the Object other to become a Rectangle. This is called class casting.
Comparison of Objects (The compareTo method)
The compareTo method is a method we want to implement if Objects are comparable.
When we create a class, we will need to specify how we will compare objects (exactly how the String class has a compareTo method that returns an int of the difference between two Strings).
Example:
public class Rectangle
…
public int compareTo(Rectangle other)
{
return getArea() – other.getArea();
}
Note: compareTo should agree with the equals method (in other words checking the same thing)
Note: The compareTo method already works for Integers, Doubles, and Strings
SEARCHING:
Sequential Search – start at index 0 and check the elements to see if they are equal to value you are searching for.
public int sequentialSearch(Object [ ] arr, Object value)
{
for (int i = 0; i < arr.length ; i++)
{
if (value.equals(arr [i]))
return i;
}
return -1;
}
Note: could use == instead of .equals if you are using primitive data.
Note: Best case number of comparisons: 1
Worse case number of comparisons: number of elements
Average case number of comparisons: number of elements/2
Binary Search - a “divide and conquer” approach that checks the middle element to determine if it is equal, less, or equal to the value we are searching for. If it is equal it returns that index, if it less than the value we are searching for, we eliminate the values prior to that number and check the values higher than that. A comparable idea is used if it is greater than the value we are searching for.
public int binarySearch (int [ ] arr, int value, int left, int right)
{
if (right < left)
return -1; // Not found
int middle = (left + right) / 2;
if (value == arr [middle] )
return middle;
else if (value < arr[middle])
return binarySearch (arr, value, left, middle - 1);
else // if ( value > arr[middle])
return binarySearch (arr, value, middle + 1, right);
}
Note: A list must be in order for binary search to work.
Note: Sequential search would be faster than binary search if the value is very close to the beginning, but in general binary search is much faster.
Note: an array with n elements, the worst case scenario is log base 2 of n (rounded down).
SORTING:
Sort: means to arrange the elements in ascending or descending order.
Selection Sort-
1. 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)
public void selectionSort (double [ ] arr)
{
for (int n = arr.length-1; n > 0; n--)
{
int maxPos = 0;
for (int k = 1; k <= n; k++)
if (arr [k] > arr [maxPos] )
maxPos = k;
//swap
double temp = arr [maxPos];
arr [maxPos] = arr [n];
arr [n] = temp;
}
}
Note: The total number of comparisons is always (no average, worst, or best case)
(n-1) + (n-2) + ... + 1 = n(n-1) / 2
Insertion Sort:
1. 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 < n)
public void insertionSort (double [ ] arr, int n)
{
for (int k = 1 ; k < n; k++)
{
double temp = arr [ k ];
int i = k;
while (i > 0 && arr [i-1] > temp)
{
arr [i] = arr [i - 1];
i --;
}
arr [i] = temp;
}
}
Note: 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.
Merge Sort:
1. Split the array into two roughly equal “halves.”
2. Sort (recursively) each half using... Mergesort.
3. Merge the two sorted halves together.