Checkpoint 3
public abstract class Collectable implements Comparable <Collectable> {
public final String masterType = "Collectable";
private String type; // extender should define their data type
// enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// this method is used to compare toString of objects
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
// static print method used by extended classes
public static void print(Collectable[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Collectable' properties
if (objs.length > 0) {
Collectable obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Collectable: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class Cupcake extends Collectable {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Cupcake.key = key;}
public enum KeyType implements KeyTypes {title, flavor, frosting, sprinkles}
// Instance data
private final String frosting;
private final int sprinkles;
private final String flavor;
private static int swap = 0;
private static int comp = 0;
// Constructor
Cupcake(String frosting, int sprinkles, String flavor)
{
this.setType("Cupcake");
this.frosting = frosting;
this.sprinkles = sprinkles;
this.flavor = flavor;
}
/* 'Collectable' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Cupcake.key; }
/* 'Collectable' requires toString override
* toString provides data based off of Static Key setting
*/
public static int getSwap(){
return swap;
}
public static int getComparison(){
return comp;
}
@Override
public String toString() {
String output="";
if (KeyType.flavor.equals(this.getKey())) {
output += this.flavor;
} else if (KeyType.frosting.equals(this.getKey())) {
output += this.frosting;
} else if (KeyType.sprinkles.equals(this.getKey())) {
output += "00" + this.sprinkles;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.flavor + ", " + this.frosting + ", " + this.sprinkles;
}
return output;
}
public static void bubbleSort(Cupcake[] cupcakes) {
boolean swapped = true;
int n = cupcakes.length;
while (swapped) {
swapped = false;
for (int i = 1; i < n; i++) {
comp++;
if (cupcakes[i - 1].compareTo(cupcakes[i]) > 0) {
Cupcake temp = cupcakes[i - 1];
cupcakes[i - 1] = cupcakes[i];
cupcakes[i] = temp;
swapped = true;
swap++;
}
}
n--;
}
}
// Test data initializer
public static Cupcake[] cupcakes() {
return new Cupcake[]{
new Cupcake("Red", 12, "Red Velvet"),
new Cupcake("Orange", 5, "Orange"),
new Cupcake("Yellow", 6, "Lemon"),
new Cupcake("Green", 7, "Apple"),
new Cupcake("Blue", 8, "Blueberry"),
new Cupcake("Purple", 9, "Blackberry"),
new Cupcake("Pink", 10, "Strawberry"),
new Cupcake("Tan", 11, "Vanilla"),
new Cupcake("Brown", 4, "Chocolate"),
};
}
public static void main(String[] args)
{
// Inheritance Hierarchy
Cupcake[] cupcakes = cupcakes(); // Array is reference type only, no methods
// print with title
Cupcake.setOrder(Cupcake.KeyType.title);
Cupcake.print(cupcakes);
// convert to Coolection and sort in flavor order
Cupcake.setOrder(Cupcake.KeyType.flavor);
bubbleSort(cupcakes); // This works because of Collectable compareTo method
Cupcake.print(cupcakes);
System.out.println("Number of swaps: " + getSwap());
System.out.println("Number of comparisons: " + getComparison());
}
}
Cupcake.main(null);
I use bubble sort here to sort the cupcakes by their flavor alphabetically. The number of swaps is 33 times, and the number of swaps is 18 times. It takes 0.5 s to run the code.
I made 2 getters getSwap() and getComparison() because I originally uses int swap = 0 and int comp = 0 in the bubble sort method, but because variable swap and comp are inside of this method, i can't just do System.out.println("Number of swaps: " + swap) in the tester method. So I moved swap and comp to the top as private static int swap = 0 and private static int comp = 0, but doing that, I will need to use getters and use them in the tester method since they are private instances.
Big O Notation
Big O Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows. In other words, it calculates the worst-case time complexity of an algorithm. Big O Notation in Data Structure describes the upper bound of an algorithm's runtime.
O(1) - Excellent/Best - algorithm processes only one statement without any iteration.
O(log n) - Good
O(n) - Fair
O(n log n) - Bad
O(n^2), O(2^n) and O(n!) - Horrible/Worst
a collection of key-value pairs, like a lookup table
import java.util.HashMap;
HashMap<String, Integer> foodIds = new HashMap<>(); //declare hashmap, key/value type have to java wrapper classes, not primitive types
foodIds.put("ramen", 12345); //add
foodIds.put("ice cream", 13579);
foodIds.put("sushi", 54321);
foodIds.put("fried rice", 831740);
System.out.println(foodIds);
System.out.println(foodIds.get("ramen")); //look up ramen's id
foodIds.put("ice cream", 24680); //overwrite current value and update new value
System.out.println(foodIds);
foodIds.replace("cake", 24680); //different from put, won't add a new one if doesn't exist
System.out.println(foodIds);
foodIds.remove("ramen"); //remove
System.out.println(foodIds);
//randomly generate 5000 elements and store them in an int array
import java.util.Random;
Random random = new Random();
int intArray[] = new int[5000];
for (int i = 0; i < intArray.length; i++) {
intArray[i] = random.nextInt(); // storing random integers in an array
}
//use the randomly generated 5000 elements
int bubbleSort[] = new int[5000];
for (int i = 0; i < bubbleSort.length; i++) {
int random = intArray[i];
bubbleSort[i] = random;
}
int comparison = 0;
int swap = 0;
public static void bubbleSort(int[] data) {
boolean swapped = true;
int n = data.length;
int i = 0;
while(swapped) {
swapped = false;
for(int j = 1; j < n - i; j++) {
if(data[j - 1] > data[j]) {
int temp = data[j - 1];
data[j - 1] = data[j];
data[j] = temp;
swapped = true;
swap++;
}
comparison++;
}
i++;
}
}
//calculate total time
long start = System.nanoTime();
bubbleSort(bubbleSort);
long end = System.nanoTime();
long timeElapsed = end - start;
//total time & number of comparisons/swaps
System.out.println("Total time: " + timeElapsed + " nanoseconds");
System.out.println("Comparisons: " + comparison);
System.out.println("Swaps: " + swap);
12 times: 33089750 37889125 23138459 21927125 21635708 22061292 25474041 25069542 20424875 22383375 22391875 22257667
average (throw out highest and lowest): 23940900
The bubble sort has a space complexity of O(1).
The number of swaps in bubble sort equals the number of inversion pairs in the given array.
When the array elements are few and the array is nearly sorted, bubble sort is effective and efficient.
//use the randomly generated 5000 elements
int mergeSort[] = new int[5000];
for (int i = 0; i < mergeSort.length; i++) {
int random = intArray[i];
mergeSort[i] = random;
}
int comparison = 0;
int swap = 0;
public void mergeSort(int data[], int l, int r) {
if (l < r) {
int m = l + (r-l)/2;
mergeSort(data, l, m);
mergeSort(data , m+1, r);
merge(data, l, m, r);
}
}
public void merge(int data[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = data[l + i];
}
for (int j = 0; j < n2; j++) {
R[j] = data[m + 1 + j];
}
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
data[k] = L[i];
i++;
}
else {
data[k] = R[j];
j++;
}
k++;
comparison++;
swap++;
}
while (i < n1) {
data[k] = L[i];
i++;
k++;
swap++;
}
while (j < n2) {
data[k] = R[j];
j++;
k++;
swap++;
}
}
//calculate total time
long start = System.nanoTime();
mergeSort(mergeSort, 0, mergeSort.length-1); //left -> 0, right -> length of mergesort
long end = System.nanoTime();
long timeElapsed = end - start;
//total time & number of comparisons/swaps
System.out.println("Total time: " + timeElapsed + " nanoseconds");
System.out.println("Comparisons: " + comparison);
System.out.println("Swaps: " + swap);
12 times: 13142708 15338583 13292792 12895541 14663292 14833125 14769292 12804833 16318958 12847708 14018666 13988792
average (throw out highest and lowest): 13979000
Time complexity:
Worst case: O(nlogn). The worst-case time complexity is the same as the best case.
Best case: O(nlogn). We are dividing the array into two sub-arrays recursively, which will cost a time complexity of O(logn). For each function call, we are calling the partition function, which costs O(n) time complexity. Hence the total time complexity is O(nlogn).
Selection Sort
In this sorting algorithm, we assume that the first element is the minimum element. Then we check to see if an element lower than the assumed minimum is present in the rest of the array. If there is, we swap the assumed minimum and the actual minimum. Otherwise, we move on to the next element.
//use the randomly generated 5000 elements
int selectionSort[] = new int[5000];
for (int i = 0; i < selectionSort.length; i++) {
int random = intArray[i];
selectionSort[i] = random;
}
int comparison = 0;
int swap = 0;
public static void selectionSort(int[] data)
{
for(int i=0;i<intArray.length; i++) {
int minIndex = i;
for(int j=i+1;j<intArray.length; j++) {
if(data[j]<data[minIndex]) {
minIndex = j;
}
comparison++;
}
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
swap++;
}
}
//calculate total time
long start = System.nanoTime();
selectionSort(selectionSort);
long end = System.nanoTime();
long timeElapsed = end - start;
//total time & number of comparisons/swaps
System.out.println("Total time: " + timeElapsed + " nanoseconds");
System.out.println("Comparisons: " + comparison);
System.out.println("Swaps: " + swap);
12 times: 18416625 24675583 19899291 18860458 20516875 25488542 19593875 21603375 20720833 20482000 18509000 18327583
average (throw out highest and lowest): 18276114
Time complexity:
Worst case: O(n²). Since we traverse through the remaining array to find the minimum for each element, the time complexity will become O(n²).
Best case: O(n²). Even if the array has already been sorted, our algorithm looks for the minimum in the rest of the array. As a result, the best-case time complexity is the same as the worst-case.
Insertion Sort
In this sorting algorithm, we check to see if the order is correct for each element until we reach the current element. Since the first element is in order, we start from the second element and check if the order is maintained. If not, then we swap them. So, on any given element, we check if the current element is greater than the previous element. If it’s not, we keep swapping elements until our current element is greater than the previous element.
//use the randomly generated 5000 elements
int insertionSort[] = new int[5000];
for (int i = 0; i < insertionSort.length; i++) {
int random = intArray[i];
insertionSort[i] = random;
}
int comparison = 0;
int swap = 0;
public static void insertionSort(int[] data)
{
for(int i = 1;i < data.length; i++) {
int j = i;
while(j > 0 && data[j] < data[j-1]) {
comparison++;
int temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
j--;
swap++;
}
}
}
//calculate total time
long start = System.nanoTime();
insertionSort(insertionSort);
long end = System.nanoTime();
long timeElapsed = end - start;
//total time & number of comparisons/swaps
System.out.println("Total time: " + timeElapsed + " nanoseconds");
System.out.println("Comparisons: " + comparison);
System.out.println("Swaps: " + swap);
12 times: 16628125 25556083 16362125 18691042 20512375 15466167 16299208 16018667 19741208 18525333 16624042 16343375
average (throw out highest and lowest): 17519300
Time complexity:
Worst case: O(n²). In a worst case situation, our array is sorted in descending order. So, for each element, we have to keep traversing and swapping elements to the left.
Best case: O(n). In the best case, our array is already sorted. So for each element, we compare our current element to the element at the left only once. Since the order is correct, we don’t swap and move on to the next element. Hence the time complexity will be O(n).
import java.util.Random;
//randomKey method
int[] randomKey = new int[100]; //int array of 100 keys
for (int i=0; i<100; i++) {
int randomNum = (int)(Math.random()*5000); //randomly generate 0-5000
randomKey[i] = randomNum; //sort in randomKey array
}
int binarySearch[] = new int[5000]; //5000 record
for (int i = 1; i < binarySearch.length-1; i++) {
binarySearch[i] = i; //store 0-5000
}
public static void binarySearch(int arr[], int first, int last, int key){
int mid = (first + last)/2;
while( first <= last ){
if ( arr[mid] < key ){ //if key is below mid (first half)
first = mid + 1;
}else if ( arr[mid] == key ){ //if key = mid
break;
}else{
last = mid - 1; //key is above mid (last half)
}
mid = (first + last)/2;
}
if ( first > last ){
System.out.println("Element is not found!");
}
}
//calculate total time
long start = System.nanoTime();
for(int i =0; i<100; i++){ //search 100 times, find 100 keys in 5000 records
binarySearch(binarySearch, 0, binarySearch.length-1, binarySearch[randomKey[i]]);
}
long end = System.nanoTime();
long timeElapsed = end - start;
//total time
System.out.println("Total time: " + timeElapsed + " nanoseconds");
12 times: 22146083 85147084 38236958 42400792 37585375 31104541 25279333 44280500 30291208 25094125 33030208 36175458
average (throw out highest and lowest): 34347800
The time complexity of the binary search algorithm is O(log n).
The best-case time complexity would be O(1) when the central index would directly match the desired value. Binary search worst case differs from that.
The worst-case scenario could be the values at either extremity of the list or values not in the list.
import java.util.HashMap;
HashMap<Integer, Integer> hashmap = new HashMap<>(); //declare hashmap, key/value type have to java wrapper classes, not primitive types
for(int i=0; i<5000; i++){
hashmap.put(i, i); //add 5000 key value pairs in hashmap
}
//calculate total time
long start = System.nanoTime();
for(int i =0; i<100; i++){ //search 100 times, find 100 keys in 5000 records
hashmap.get(randomKey[i]);
}
long end = System.nanoTime();
long timeElapsed = end - start;
//total time
System.out.println("Total time: " + timeElapsed + " nanoseconds");
12 times: 29524917 26524416 38187625 35060125 38538542 49850750 39018792 35456125 29634542 32697208 29407792 26733166
average (throw out highest and lowest): 33637500
Comprison/Analysis
binary search - 34347800
hashmap lookup - 33637500
The performance is the same. However, in the average case scenario, hash lookup is significantly faster than binary search. In real applications, we mainly consider an average case scenario in order to test and compare the performance of different methods