Hacks for DS Sorts
Sort analysis and building hashmaps
Hacks
Analyze the Big O complexity on Sorts.
- Establish analytics including:time to sort, number of comparisons and number of swaps.- Average the results for each each Sort, run each at least 12 times and 5000 elements. You should throw out High and Low when doing analysis.
- Make your final/judgement on best sort: Number of Comparisons, Number of Swaps, Big O complexity, and Total Time.
public class SortAnalysis {
// generate array of 5000 integers
public static int[] generateArray() {
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 10000);
}
return arr;
}
public static float[] main(String[] args) {
System.out.println("-------------------------------");
// create an array with 5000 elements
int[] arr1 = generateArray();
int[] arr2 = new int[5000];
int[] arr3 = new int[5000];
int[] arr4 = new int[5000];
System.arraycopy(arr1, 0, arr2, 0, 500);
System.arraycopy(arr1, 0, arr3, 0, 500);
System.arraycopy(arr1, 0, arr4, 0, 500);
float[] times = new float[4];
String str = "";
// sort the array
long start = System.nanoTime();
bubbleSort(arr1);
long end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns | ");
times [0] = (end - start);
start = System.nanoTime();
mergeSort(arr2);
end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns | ");
times [1] = (end - start);
start = System.nanoTime();
selectionSort(arr3);
end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns | ");
times [2] = (end - start);
start = System.nanoTime();
insertionSort(arr4);
end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns");
times [3] = (end - start);
System.out.println(str);
return times;
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// instertionsort from before
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int j = i - 1;
while (j >= 0 && current < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}
// selectionsort from before
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// mergesort from previous lesson
public static void mergeSort(int[] arr) {
if (arr.length > 1) {
int[] left = leftHalf(arr);
int[] right = rightHalf(arr);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
}
// lefthalf function for mergesort
public static int[] leftHalf(int[] arr) {
int size1 = arr.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = arr[i];
}
return left;
}
// righthalf function for mergesotr
public static int[] rightHalf(int[] arr) {
int size1 = arr.length / 2;
int size2 = arr.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++) {
right[i] = arr[i + size1];
}
return right;
}
public static int[] merge(int[] result, int[] left, int[] right) {
int i1 = 0;
int i2 = 0;
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1];
i1++;
} else {
result[i] = right[i2];
i2++;
}
}
return result;
}
}
System.out.println("Bubble | Merge | Selection | Insertion");
float[] means = new float[4];
for (int i = 0; i < 12; i++) {
float[] a = SortAnalysis.main(null);
for (int j = 0; j < 4; j++) {
means[j] += a[j];
}
}
for (int i = 0; i < 4; i++) {
means[i] /= 12;
means[i] = Math.round(means[i] * 1000) / 1000;
}
System.out.println("-------------------------------");
System.out.println("Average: " + means[0] + "ns | " + means[1] + "ns | " + means[2] + "ns | " + means[3] + "ns");
- Bubble complexity: O(n^2) - but best case scenario is O(n) only if the list is already sorted
- Merge complexity: O(n log n)
- Selection complexity: O(n^2) regardless of the order
- Insertion complexity: O(n^2) - best case scenario is also O(n) if sorted
import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;
public class HashTester {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] arr = new int[500000];
for (int i = 0; i < 500000; i++) {
Integer value = (int) (Math.random() * 500000);
map.put(value, value);
arr[i] = value;
}
System.out.println("LookUp | BinarySearch");
System.out.println("-------------------------------");
double total_lut = 0;
double total_bst = 0;
// get num to search for from scanner
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number to search for: ");
Integer num = sc.nextInt();
for (int i = 0; i < 12; i++) {
// check look up time for hash map
String str = "| ";
long lut = (lookUp(map, num));
total_lut += lut;
str += (lut + "ns | ");
// copy array, check binary search time
int[] arra = new int[500000];
System.arraycopy(arr, 0, arra, 0, arr.length);
long bst = (binarySearchTime(arra, num));
total_bst += bst;
str += (bst + "ns | ");
System.out.println(str);
}
System.out.println("-------------------------------");
System.out.println("Average: " + (total_lut / 12) + "ns | " + (total_bst / 12) + "ns");
}
public static long lookUp(HashMap<Integer, Integer> map, Integer value) {
long start = System.nanoTime();
map.containsKey(value);
long end = System.nanoTime();
return (end - start);
}
public static long binarySearchTime(int[] arr, Integer value) {
long start = System.nanoTime();
// binary search
int low = 0;
int high = arr.length - 1;
int mid = (low + high) / 2;
while (low <= high) {
if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] == value) {
break;
} else {
high = mid - 1;
}
mid = (low + high) / 2;
}
long end = System.nanoTime();
return (end - start);
}
}
HashTester.main(null);
Pros and Cons of Collection vs HashMap
| Collections | HashMaps | ||
|---|---|---|---|
| Pros | Cons | Pros | Cons |
| Store and manipulate groups of objects | Java doesn't integrate any methods to search or sort | Map keys to values | More memory usage than collections |
| Order of elements in a group, can reorder them too | Inefficient at getting a specific value | Retrieving a value from a key is very fast | No order of elements, no sorting |
| Easy for simple uses like when you don't need key:value pairs | Key:value mapping isn't a thing | Built-in methods for search/sort such as containsKey() or getValue() | Starts to get a bit weird / errors with duplicate keys |