Checkpoint 3 Post
Checkpoint 3 blog post for AP CSA
import java.util.LinkedList;
public class Sorting {
// Initialize different Linked Lists to be sorted
public LinkedList<Integer> linkedListName = new LinkedList<Integer>();
public LinkedList<Integer> linkedListNameBubble = new LinkedList<Integer>();
public LinkedList<Integer> linkedListNameSelection = new LinkedList<Integer>();
public LinkedList<Integer> linkedListNameInsertion = new LinkedList<Integer>();
public LinkedList<Integer> linkedListNameMerge = new LinkedList<Integer>();
public Sorting(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
linkedListName.add(numbers[i]);
linkedListNameBubble.add(numbers[i]);
linkedListNameSelection.add(numbers[i]);
linkedListNameInsertion.add(numbers[i]);
linkedListNameMerge.add(numbers[i]);
}
}
// Iterate through each element of the linked list, and in each iteration, swap 2 elements if they are not in the correct order.
// After one full loop of the linked list, decrease the loop condition by one, since the last element has to be the highest in the linked list.
public void bubbleSort() {
int capacity = linkedListNameBubble.size() - 1;
for (int i = 0; i < capacity; i++) {
if (linkedListNameBubble.get(i) > linkedListNameBubble.get(i + 1)) {
int temp = linkedListNameBubble.get(i + 1);
linkedListNameBubble.set(i + 1, linkedListNameBubble.get(i));
linkedListNameBubble.set(i, temp);
}
if (i == capacity - 1 && capacity > 0) {
capacity--;
i = -1;
}
}
}
// In one loop of the selection sort, the algorithm finds the minimum value of the linked list.
// After one full loop, the minimum value is set at the minimum index, and the starting index of the loop moves up by one.
public void selectionSort() {
int tempIndex = 0;
for (int i = tempIndex; i < linkedListNameSelection.size(); i++) {
int min = linkedListNameSelection.get(tempIndex);
int minIndex = tempIndex;
if (i == tempIndex) {
min = linkedListNameSelection.get(i);
} else if (linkedListNameSelection.get(i) < min) {
minIndex = i;
min = linkedListNameSelection.get(i);
}
int temp = linkedListNameSelection.get(tempIndex);
linkedListNameSelection.set(tempIndex, min);
linkedListNameSelection.set(minIndex, temp);
if (i == linkedListNameSelection.size() - 1 && tempIndex < linkedListNameSelection.size() - 2) {
tempIndex++;
i = tempIndex - 1;
}
}
}
// In each iteration, take the current element and compare it to all of the other elements in the linked list, then insert it to the position before the first element it is lower than in value.
public void insertionSort() {
for (int i = 0; i < linkedListNameInsertion.size(); i++) {
for (int j = 0; j < i; j++) {
if (linkedListNameInsertion.get(j) > linkedListNameInsertion.get(i)) {
int temp = linkedListNameInsertion.get(j);
linkedListNameInsertion.set(j, linkedListNameInsertion.get(i));
linkedListNameInsertion.remove(i);
linkedListNameInsertion.add(j + 1, temp);
break;
}
}
}
}
public static void main(String[] args) {
int[] numbers = {1, 7, 2, 5, 3, 6, 4, 8};
Sorting myObj = new Sorting(numbers);
System.out.println("LinkedList before bubble sort: " + myObj.linkedListName.toString());
myObj.bubbleSort();
System.out.println("LinkedList after bubble sort: " + myObj.linkedListNameBubble.toString());
System.out.println("LinkedList before selection sort: " + myObj.linkedListName.toString());
myObj.selectionSort();
System.out.println("LinkedList after selection sort: " + myObj.linkedListNameSelection.toString());
System.out.println("LinkedList before insertion sort: " + myObj.linkedListName.toString());
myObj.insertionSort();
System.out.println("LinkedList after insertion sort: " + myObj.linkedListNameInsertion.toString());
}
}
Sorting.main(null);
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 Sport extends Collectable {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Sport.key = key;}
public enum KeyType implements KeyTypes {title, name, numPlayers}
// Instance data
private final String name;
private final int numPlayers;
// Constructor
Sport(String name, int numPlayers)
{
this.setType("Sport");
this.name = name;
this.numPlayers = numPlayers;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Sport.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString() {
String output="";
if (KeyType.name.equals(this.getKey())) {
output += this.name;
} else if (KeyType.numPlayers.equals(this.getKey())) {
output += "00" + this.numPlayers;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.name + ", " + this.numPlayers;
}
return output;
}
// Test data initializer
public static Sport[] sports() {
return new Sport[]{
new Sport("Soccer", 22),
new Sport("Basketball", 10),
new Sport("Volleyball", 12),
new Sport("Tennis", 2),
new Sport("Football", 22)
};
}
public static void main(String[] args)
{
// Inheritance Hierarchy
Sport[] objs = sports();
// print with title
Sport.setOrder(KeyType.title);
Sport.print(objs);
// print flavor only
Sport.setOrder(KeyType.name);
Sport.print(objs);
// print numPlayers only
Sport.setOrder(KeyType.numPlayers);
Sport.print(objs);
}
}
Sport.main(null);
Big O Complexity Notes
- Space complexity is basically the total amount of memory space used by a certain program, and it includes space allocated to input values.
- Time complexity is basically the total amount of time it takes to run a certain program.
- An ideal program involves low space complexity and low time complexity, as it minimizes the amount of resources that need to be used.
import java.util.*;
public class BigOAnalyze {
public int[] numbers = new int[5000];
public BigOAnalyze() {
for (int i = 0; i < numbers.length; i++) {
numbers[i] = (int) (Math.random() * 1000);
}
}
public void bubbleSort() {
int capacity = numbers.length - 1;
for (int i = 0; i < capacity; i++) {
if (numbers[i] > numbers[i + 1]) {
int temp = numbers[i + 1];
numbers[i + 1] = numbers[i];
numbers[i] = temp;
}
if (i == capacity - 1 && capacity > 0) {
capacity--;
i = -1;
}
}
}
public void selectionSort() {
int tempIndex = 0;
for (int i = tempIndex; i < numbers.length; i++) {
int min = numbers[tempIndex];
int minIndex = tempIndex;
if (i == tempIndex) {
min = numbers[i];
} else if (numbers[i] < min) {
minIndex = i;
min = numbers[i];
}
int temp = numbers[tempIndex];
numbers[tempIndex] = min;
numbers[minIndex] = temp;
if (i == numbers.length - 1 && tempIndex < numbers.length - 2) {
tempIndex++;
i = tempIndex - 1;
}
}
}
public void insertionSort() {
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < i; j++) {
if (numbers[j] > numbers[i]) {
for (int x = i; x > j; x--) {
int temp = numbers[x];
numbers[x] = numbers[x-1];
numbers[x-1] = temp;
}
break;
}
}
}
}
public static void main(String[] args) {
int averageBubbleTime = 0;
int averageSelectionTime = 0;
int averageInsertionTime = 0;
for (int i = 0; i < 12; i++) {
BigOAnalyze myObj = new BigOAnalyze();
long startTime = System.currentTimeMillis();
myObj.bubbleSort();
long stopTime = System.currentTimeMillis();
long time = stopTime - startTime;
averageBubbleTime += time;
System.out.println("Bubble sort time: " + time);
BigOAnalyze myObj2 = new BigOAnalyze();
startTime = System.currentTimeMillis();
myObj2.selectionSort();
stopTime = System.currentTimeMillis();
time = stopTime - startTime;
averageSelectionTime += time;
System.out.println("Selection sort time: " + time);
BigOAnalyze myObj3 = new BigOAnalyze();
startTime = System.currentTimeMillis();
myObj3.insertionSort();
stopTime = System.currentTimeMillis();
time = stopTime - startTime;
averageInsertionTime += time;
System.out.println("Insertion sort time: " + time);
}
averageBubbleTime /= 12;
averageSelectionTime /= 12;
averageInsertionTime /= 12;
System.out.println("Average bubble sort time: " + averageBubbleTime);
System.out.println("Average selection sort time: " + averageSelectionTime);
System.out.println("Average insertion sort time: " + averageInsertionTime);
}
}
BigOAnalyze.main(null);
Big O Analysis:
- Bubble Sort:
- Space complexity: O(1)
- Time complexity: O(n^2)
- Selection sort:
- Space complexity: o(1)
- Time complexity: o(n^2)
- Insertion sort:
- Space complexity: o(1)
- Time complexity: o(n)
- In our program, the insertion sort took the least time to perform its task. Since the space complexities are about the same for all three sorts, I believe the insertion sort is the most optimal.
HashMap
import java.util.HashMap;
import java.util.Scanner;
public class MapAnalyze {
public long hashMapAnalyze(HashMap<Integer, Integer> numbersMap, int inputNumber) {
long startTime = System.currentTimeMillis();
numbersMap.containsValue(inputNumber);
long stopTime = System.currentTimeMillis();
long time = stopTime - startTime;
return time;
}
public int[] bubbleSort(int[] numbers) {
int capacity = numbers.length - 1;
for (int i = 0; i < capacity; i++) {
if (numbers[i] > numbers[i + 1]) {
int temp = numbers[i + 1];
numbers[i + 1] = numbers[i];
numbers[i] = temp;
}
if (i == capacity - 1 && capacity > 0) {
capacity--;
i = -1;
}
}
return numbers;
}
public long binarySearchAnalyze(int[] numbers, int inputNumber) {
int[] newNumbers = bubbleSort(numbers);
long startTime = System.currentTimeMillis();
int midIndex = newNumbers.length/2;
int length = newNumbers.length/2;
while(length > 1) {
if (newNumbers[midIndex] == inputNumber) {
break;
} else if (newNumbers[midIndex] > inputNumber) {
length /= 2;
midIndex -= length;
} else if (newNumbers[midIndex] < inputNumber) {
length /= 2;
midIndex += length;
}
}
long stopTime = System.currentTimeMillis();
long time = stopTime - startTime;
return time;
}
public static void main(String[] args) {
int[] numbers = new int[5000];
HashMap<Integer, Integer> numbersMap = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = (int) (Math.random() * 1000);
numbersMap.put(i, (int) (Math.random() * 1000));
}
MapAnalyze myObj = new MapAnalyze();
Scanner userInput = new Scanner(System.in);
System.out.println("Enter a number between 1 and 1000:");
int inputNumber = userInput.nextInt();
System.out.println("Time for binary search: " + myObj.hashMapAnalyze(numbersMap, inputNumber));
System.out.println("Time for HashMap lookup: " + myObj.binarySearchAnalyze(numbers, inputNumber));
}
}
MapAnalyze.main(null);
| Collection | HashMap |
|---|---|
| Pros | Pros |
| + Simple | + Fast access and retrieval |
| + Stores a lot of data, | + Efficient for large data sets |
| can iterate over small | + Provides key-value pairs |
| data sets | + No duplicates allowed |
| + Allows duplicates to emerge in multiple indexes | |
| --------------------------- | ------------------------------ |
| Cons | Cons |
| - Slower | - Complexity |
| - No efficient key-based | - memory-intensive |
| access | - Not thread-safe |
| - No order like, only based on a key | - Requires more code to |
| iterate, not as |