Sort, Space and Time Complexity
Hashmaps and Big O Hack 1
- 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 AnalysisOnSorts {
// generate array of 5000 integers
public static int[] GenerateDataForSortTest() {
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 9999);
}
return arr;
}
// insertion sort code
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}
// selection sort code
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
// bubble sort code
public static void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
public static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/*Copy data to temp arrays*/
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// mergeSort
public static void mergeSort(int arr[], int left, int right)
{
if (left < right) {
// Find the middle point
int middle = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
public static float[] sortWithAlgosAndPrint() {
System.out.println("---------------------------------------------------------------------------------------------");
// create an array with 5000 elements
int[] dataSet1 = GenerateDataForSortTest();
int[] dataSet2 = new int[5000];
int[] dataSet3 = new int[5000];
int[] dataSet4 = new int[5000];
System.arraycopy(dataSet1, 0, dataSet2, 0, 5000);
System.arraycopy(dataSet1, 0, dataSet3, 0, 5000);
System.arraycopy(dataSet1, 0, dataSet4, 0, 5000);
float[] sortTimeTaken = new float[4];
long startTime = System.nanoTime();
insertionSort(dataSet1);
long endTime = System.nanoTime();
sortTimeTaken [0] = (endTime - startTime);
startTime = System.nanoTime();
selectionSort(dataSet2);
endTime = System.nanoTime();
sortTimeTaken [1] = (endTime - startTime);
startTime = System.nanoTime();
bubbleSort(dataSet3);
endTime = System.nanoTime();
sortTimeTaken [2] = (endTime - startTime);
startTime = System.nanoTime();
mergeSort(dataSet4, 0, dataSet4.length -1 );
endTime = System.nanoTime();
sortTimeTaken [3] = (endTime - startTime);
for(int i = 0 ; i< 4; i++ ){
System.out.print (sortTimeTaken[i] + " nano secs ---- ");
}
System.out.println("");
return sortTimeTaken;
}
public static void main(String[] args) {
System.out.println("Insertion Sort ---- Selection Sort ---- Bubble Sort ---- Merge Sort");
float[] avgs = new float[4];
for (int i = 0; i < 12; i++) {
float[] a = sortWithAlgosAndPrint();
for (int j = 0; j < 4; j++) {
avgs[j] += a[j];
}
}
for (int i = 0; i < 4; i++) {
avgs[i] /= 12;
avgs[i] = Math.round(avgs[i] * 1000) / 1000;
}
System.out.println(" ========================================================================================= ");
System.out.println("Average: " + avgs[0] + " nano secs ---- " + avgs[1] + " nano secs ---- " + avgs[2] + " nano secs ---- " + avgs[3] + " nano secs ---- ");
}
}
AnalysisOnSorts.main(null);
- Insertion Sort analysis: Runs at O(n^2)
- The best case scenario is O(n) if sorted
- Selection Sort analysis: Runs at O(n^2)
- This is regardless of the order the integers come at
- Bubble Sort analysis: Runs at O(n^2)
- The best case scenario for a bubble sort is O(n)
- This is only if the list has already been sorted
- The best case scenario for a bubble sort is O(n)
- Merge Sort analysis: Runs at O(n log n)
Hashmaps and Big O Hack 2
- Build your own Hashmap. Make a HashMap to correspond to a Data Structure using a Collection.
- Be sure to have 5000 records
- Perform analysis on Binary Search vs HashMap Lookup, try using random to search and find 100 keys in 5000 records. Perform 12 times and throw out high and low.
import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;
public class HashMapVSBinarySearch {
public static long hashMapFind(HashMap<Integer, Integer> map, Integer value) {
long startTime = System.nanoTime();
map.containsKey(value);
long endTime = System.nanoTime();
return (endTime - startTime);
}
public static long binarySearchFind(int[] arr, Integer value) {
long startTime = System.nanoTime();
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 endTime = System.nanoTime();
return (endTime - startTime);
}
public static void main(String[] args) {
HashMap<Integer, Integer> mapDataSet = new HashMap<Integer, Integer>();
int[] bsDataSet = new int[5000];
for (int i = 0; i < 5000; i++) {
Integer value = (int) (Math.random() * 9999);
mapDataSet.put(value, value);
bsDataSet[i] = value;
}
System.out.println("HashMap find | BinarySearch");
System.out.println("-------------------------------");
double totalTimeTakenMap = 0;
double totalTimeTakenBS = 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();
System.out.println("Time Taken to search " + num + " with " );
System.out.println("| BinarySearch | HashMap | ");
System.out.println("==========================================");
for (int i = 0; i < 12; i++) {
// check look up time for hash map
String str = "| ";
long timeTaken = binarySearchFind(bsDataSet, num);
totalTimeTakenBS += timeTaken;
str += (timeTaken + " ns | ");
timeTaken = hashMapFind(mapDataSet, num);
totalTimeTakenMap += timeTaken;
str += (timeTaken + " ns | ");
System.out.println(str);
}
System.out.println("==========================================");
System.out.println("Average: " + (totalTimeTakenBS / 12) + " ns | " + (totalTimeTakenMap / 12) + " ns");
}
}
HashMapVSBinarySearch.main(null);
Hashmaps and Big O Extra Hack
- Extra, Practical learning
- Performing Iteration, Delete, and Add operations are another way to analyze Collection vs HashMap data structure.
- A HashMap and a Collection can be used in a Class, POJO and API.
- Make a Diagram on the Pros and Cons of Collection vs HashMap
Pros and Cons of Collection vs HashMap
| HashMaps | Collections | ||
|---|---|---|---|
| Pros | Cons | Pros | Cons |
| Built-in methods for search/sort such as containsKey() or getValue() | No order of elements, no sorting | Easy for simple uses like when you don't need key:value pairs | Java doesn't integrate any methods to search or sort |
| Retrieving a value from a key is very fast | More memory usage than collections | Order of elements in a group, can reorder them too | Key:value mapping isn't a thing |
| Map keys to values | Starts to get a bit weird / errors with duplicate keys | Store and manipulate groups of objects | Inefficient at getting a specific value |