Hashmaps, Sorts, and Collegeboard
Different sorts comparing to each other and hashmap searches.
import java.util.HashMap;
import java.util.Random;
public class BookCollection {
public static void main(String[] args) {
HashMap<String, String> bookMap = new HashMap<String, String>();
// Add 5000 books and authors to the map
for (int i = 0; i < 5000; i++) {
String isbn = "ISBN" + i;
String author = "Author" + i;
bookMap.put(isbn, author);
}
// Test performance of binary search vs HashMap lookup
Random rand = new Random();
int[] searchKeys = new int[100];
for (int i = 0; i < 100; i++) {
searchKeys[i] = rand.nextInt(5000);
}
// Binary search
long binarySearchTime = 0;
for (int i = 0; i < 12; i++) {
long startTime = System.nanoTime();
for (int j = 0; j < 100; j++) {
String author = binarySearch(bookMap, searchKeys[j]);
}
long endTime = System.nanoTime();
long elapsedTime = endTime - startTime;
binarySearchTime += elapsedTime;
}
System.out.println("Binary search average time: " + (binarySearchTime / 12) + " nanoseconds");
// HashMap lookup
long hashMapLookupTime = 0;
for (int i = 0; i < 12; i++) {
long startTime = System.nanoTime();
for (int j = 0; j < 100; j++) {
String author = bookMap.get("ISBN" + searchKeys[j]);
}
long endTime = System.nanoTime();
long elapsedTime = endTime - startTime;
hashMapLookupTime += elapsedTime;
}
System.out.println("HashMap lookup average time: " + (hashMapLookupTime / 12) + " nanoseconds");
}
// Binary search implementation
public static String binarySearch(HashMap<String, String> bookMap, int key) {
String[] keys = bookMap.keySet().toArray(new String[bookMap.size()]);
int low = 0;
int high = keys.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
String isbn = keys[mid];
int isbnNum = Integer.parseInt(isbn.substring(4));
if (isbnNum == key) {
return bookMap.get(isbn);
} else if (isbnNum < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return null;
}
}
BookCollection.main(null);
import java.util.Arrays;
public class SortComparison {
private static int comparisons;
private static int swaps;
public static void selectionSort(int[] arr) {
int n = arr.length;
int comparisons = 0;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
comparisons++;
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
swaps++;
}
System.out.println("Selection Sort - Comparisons: " + comparisons + " Swaps: " + swaps);
}
public static void insertionSort(int[] arr) {
int n = arr.length;
int comparisons = 0;
int swaps = 0;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
comparisons++;
arr[j + 1] = arr[j];
j = j - 1;
swaps++;
}
arr[j + 1] = key;
swaps++;
}
System.out.println("Insertion Sort - Comparisons: " + comparisons + " Swaps: " + swaps);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void merge(int[] arr, 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] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
comparisons++; // increment comparisons for each comparison made
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr1, arr2, arr3;
// Selection Sort
long start1 = System.nanoTime();
for (int i = 0; i < 12; i++) {
arr1 = new int[5000];
arr2 = new int[5000];
arr3 = new int[5000];
for (int j = 0; j < 5000; j++) {
int n = (int) (Math.random() * 10000);
arr1[j] = n;
arr2[j] = n;
arr3[j] = n;
}
int[] temp = Arrays.copyOf(arr1, arr1.length);
selectionSort(temp);
}
long end1 = System.nanoTime();
long time1 = end1 - start1;
// Insertion Sort
long start2 = System.nanoTime();
for (int i = 0; i < 12; i++) {
arr1 = new int[5000];
arr2 = new int[5000];
arr3 = new int[5000];
for (int j = 0; j < 5000; j++) {
int n = (int) (Math.random() * 10000);
arr1[j] = n;
arr2[j] = n;
arr3[j] = n;
}
int[] temp = Arrays.copyOf(arr2, arr2.length);
insertionSort(temp);
}
long end2 = System.nanoTime();
long time2 = end2 - start2;
// Merge Sort
long start3 = System.nanoTime();
for (int i = 0; i < 12; i++) {
arr1 = new int[5000];
arr2 = new int[5000];
arr3 = new int[5000];
for (int j = 0; j < 5000; j++) {
int n = (int) (Math.random() * 10000);
arr1[j] = n;
arr2[j] = n;
arr3[j] = n;
}
int[] temp = Arrays.copyOf(arr3, arr3.length);
comparisons = 0; // reset comparisons before each run
mergeSort(temp, 0, temp.length - 1);
System.out.println("Merge Sort - Comparisons: " + comparisons);
}
long end3 = System.nanoTime();
long time3 = end3 - start3;
System.out.println("Average time taken for Selection Sort: " + (time1 / 12) + " ns");
System.out.println("Average time taken for Insertion Sort: " + (time2 / 12) + " ns");
System.out.println("Average time taken for Merge Sort: " + (time3 / 12) + " ns");
System.out.println("Best sort based on comparisons: Merge Sort");
System.out.println("Best sort based on swaps: Insertion Sort");
System.out.println("Best sort based on Big O complexity: Merge Sort");
System.out.println("Best sort based on total time: Merge Sort");
}
}
SortComparison.main(null);
| Collection | HashMap |
|---|---|
| Pros: | Pros: |
| - Simple and easy to use | - Fast lookup and insertion |
| - Allows duplicates | - Provides key-value mapping |
| - Preserves insertion order | - Supports null keys and values |
| Cons: | Cons: |
| - Slower for large collections | - More complex to use than Collection |
| - No efficient way to search for an element | - Can cause collisions |
| - No key-value mapping | - Does not preserve insertion order |
| - Does not support null values | - Not thread-safe by default |