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.

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.

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

Generate 5000 random Integers into an int Array 

import java.util.Random;
Random num = new Random();
int arr[] = new int[5000];
for (int i = 0; i < arr.length; i++) {
    arr[i] = num.nextInt(); // storing random integers in an array
}

Analyze the Big O complexity on Sorts.(Bubble sort)

  • Results:
time to sort ( Nanoseconds ) number of comparisons number of swaps
40948868 24995000 18711184
33597371 24995000 18711184
35568813 24995000 18711184
41071490 24995000 18711184
32054804 24995000 18711184
53361763 24995000 18711184
30094006 24995000 18711184
65122703 24995000 18711184
30226742 24995000 18711184
37281759 24995000 18711184
39752651 24995000 18711184
47037993 24995000 18711184
  • Average Result ( throw out High and Low ) :
time to sort ( Nanoseconds ) number of comparisons number of swaps
39090225.4 ( 0.03909023 sec ) 24995000 18711184
  • Big O complexity:
  1. Worst case: O(n²).
  2. Best case: O(n). if array is already sorted.
int numOfComparisons = 0;
int numberOfSwaps = 0;

public static void bubbleSort (int[] data)
{
    for(int i = 0;i < data.length; i++){
        for(int j=0;j < data.length - 1; j++){
            if(data[j] > data[j+1]){
                int temp = arr[j];
                data[j] = data[j+1];
                data[j+1] = temp;
                numberOfSwaps++;
           }
           numOfComparisons++;
        }
    }
}
//----------------------------------------------------------------------
int bubbleSortTester[] = new int[5000];
for (int i = 0; i < bubbleSortTester.length; i++) {
    int num = arr[i];
    bubbleSortTester[i] = num; // storing random integers in an array
}
long start = System.nanoTime();
bubbleSort(bubbleSortTester); 
long finish = System.nanoTime();
long timeElapsed = finish - start;
System.out.println("Nanoseconds: " + timeElapsed);
System.out.println("number of comparisons: " + numOfComparisons);
System.out.println("number of Swaps: " + numberOfSwaps);

Nanoseconds: 47037993
number of comparisons: 24995000
number of Swaps: 11459686

Analyze the Big O complexity on Sorts.(Selection Sort)

  • Results:
time to sort number of comparisons number of swaps
25184109 12497500 5000
36724410 12497500 5000
19282268 12497500 5000
27323052 12497500 5000
32623821 12497500 5000
24525162 12497500 5000
21620519 12497500 5000
21299771 12497500 5000
20977239 12497500 5000
22184216 12497500 5000
25525767 12497500 5000
38868922 12497500 5000
  • Average Result ( throw out High and Low ) :
time to sort number of comparisons number of swaps
25798806.6 ( 0.02579881 sec ) 12497500 5000
  • Big O complexity:
  1. 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²).
  2. 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.
int numOfComparisons = 0;
int numberOfSwaps = 0;

public static void selectionSort(int[] data)
{
    for(int i=0;i<arr.length; i++) {
        int minIndex = i;  
        for(int j=i+1;j<arr.length; j++) {
           if(data[j]<data[minIndex]) {
             minIndex = j;
          }
          numOfComparisons++;
        }
      int temp = data[i];
      data[i] = data[minIndex];
      data[minIndex] = temp;
      numberOfSwaps++;
    }
}
//---------------------------------------------------------------------------
int selectionSortTester[] = new int[5000];
for (int i = 0; i < selectionSortTester.length; i++) {
    int num = arr[i];
    selectionSortTester[i] = num; // storing random integers in an array
}
long start = System.nanoTime();
selectionSort(selectionSortTester); 
long finish = System.nanoTime();
long timeElapsed = finish - start;
System.out.println("Nanoseconds: " + timeElapsed);
System.out.println("number of comparisons: " + numOfComparisons);
System.out.println("number of Swaps: " + numberOfSwaps);

Nanoseconds: 38868922
number of comparisons: 12497500
number of Swaps: 5000

Analyze the Big O complexity on Sorts.(Insertion Sort)

  • Results:
time to sort number of comparisons number of swaps
12123437 6150953 6150953
13525997 6150953 6150953
17174613 6150953 6150953
19307095 6150953 6150953
16558676 6150953 6150953
15294102 6150953 6150953
12936251 6150953 6150953
28740336 6150953 6150953
14485925 6150953 6150953
15376347 6150953 6150953
15016661 6150953 6150953
17482556 6150953 6150953
  • Average Result ( throw out High and Low ) :
time to sort number of comparisons number of swaps
15715822.3 ( 0.01571582 sec ) 6150953 6150953
  • Big O complexity:
  1. 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.
  2. 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).1. 
int numOfComparisons = 0;
int numberOfSwaps = 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]) {
            numOfComparisons++;
            int temp = data[j];
            data[j] = data[j-1];
            data[j-1] = temp;
            j--;
            numberOfSwaps++;
        }
    }
}

//---------------------------------------------------------------------------
int InsertionSortTester[] = new int[5000];
for (int i = 0; i < InsertionSortTester.length; i++) {
    int num = arr[i];
    InsertionSortTester[i] = num; // storing random integers in an array
}
long start = System.nanoTime();
insertionSort(InsertionSortTester); 
long finish = System.nanoTime();
long timeElapsed = finish - start;

System.out.println("Nanoseconds: " + timeElapsed);
System.out.println("number of comparisons: " + numOfComparisons);
System.out.println("number of Swaps: " + numberOfSwaps);

Nanoseconds: 18049781
number of comparisons: 6150953
number of Swaps: 6150953

Analyze the Big O complexity on Sorts.(Merge Sort)

  • Results:
time to sort number of comparisons number of swaps
9317561 55175 61808
12992589 55175 61808
19746831 55175 61808
12912218 55175 61808
12534219 55175 61808
16034847 55175 61808
17103831 55175 61808
18385908 55175 61808
19866444 55175 61808
10257987 55175 61808
16992695 55175 61808
11263257 55175 61808
  • Average Result ( throw out High and Low ) :
time to sort number of comparisons number of swaps
14822438.2 ( 0.01482244 sec ) 55175 61808
  • Big O complexity:
  1. Worst case: O(nlogn). The worst-case time complexity is the same as the best case.
  2. 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).
int numOfComparisons = 0;
int numberOfSwaps = 0;

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 i = 0;i < n2; i++) {
        R[i] = data[m+1+i];
    }
    int i = 0, j = 0, k =l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            data[k++] = L[i++];
            numOfComparisons++;
            numberOfSwaps++;
        }
        else {
            data[k++] = R[j++];
            numOfComparisons++;
            numberOfSwaps++;
        }
    }
    while(i < n1) {
        data[k++] = L[i++];
        numberOfSwaps++;
    }
    while(j < n2) {
        data[k++] = R[j++];
        numberOfSwaps++;
    }
}
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);
    }
}

//---------------------------------------------------------------------------
int[] MergeSortTester = new int[5000];
for (int i = 0; i < MergeSortTester.length; i++) {
    int num = arr[i];
    MergeSortTester[i] = num;
}
long start = System.nanoTime();
mergeSort(MergeSortTester, 0, MergeSortTester.length-1);
long finish = System.nanoTime();
long timeElapsed = finish - start;
System.out.println("Nanoseconds: " + timeElapsed);
System.out.println("number of comparisons: " + numOfComparisons);
System.out.println("number of Swaps: " + numberOfSwaps);

Nanoseconds: 11263257
number of comparisons: 55264
number of Swaps: 61808
Sort time to sort number of comparisons number of swaps
Bubble 39090225.4 ( 0.03909023 sec ) 24995000 18711184
Selection 25798806.6 ( 0.02579881 sec ) 12497500 5000
Insertion 15715822.3 ( 0.01571582 sec ) 6150953 6150953
Merge 14822438.2 ( 0.01482244 sec ) 55175 61808

Hashmap(Binary Search vs. HashMap Lookup)

HashMap Random Lookup

  • Results:
time to search 100 random keys ( Nanoseconds )
11207453
10757380
13337548
11290346
12568205
10702041
12140286
11913891
17251758
12408096
12752262
12379735
  • Average Result ( throw out High and Low ) :
time to search
12075520.2 ( 0.01207552 sec )
  • O(1)
import java.util.Random;
int[] randomKey = new int[100];
for(int i =0; i<100; i++){   
    int random = (int)(Math.random()*5000);          //random search by 100 keys
    randomKey[i] = random;
}

Map<String, Integer> myHashMap = new HashMap<>();
for (int i = 0; i < 5000; i++) {
    myHashMap.put("apple" + i, i); // storing random integers
}

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

long start = System.nanoTime();
for(int i =0; i<100; i++){            
    myHashMap.get("apple" + randomKey[i]);
}
long finish = System.nanoTime();
long timeElapsed = finish - start;
System.out.println();
System.out.println("Nanoseconds: " + timeElapsed);

Nanoseconds: 25256792
  • Results:
time to search 100 random keys ( Nanoseconds )
10744880
14870334
17765997
15532206
19414759
16884201
13640847
22480933
14822539
17184193
24756768
14169391
  • Average Result ( throw out High and Low ) :
time to search
16676540 ( 0.01667654 sec )
  • The time complexity of binary search is O(log n)
int binarySearchTester[] = new int[5000];
for (int i = 0; i < binarySearchTester.length; i++) {
    binarySearchTester[i] = i; // storing random integers in an array
}

public static int binarySearch(int numArray[], int number_to_search_for) {
  int low = 0;
  int high = numArray.length - 1;
  
  while (low <= high){
    int middleIndex = (low + high) / 2;
      
    if (number_to_search_for == numArray[middleIndex]){
        return middleIndex;
    }
    if (number_to_search_for < numArray[middleIndex]){
        high = middleIndex - 1;
    }
    if (number_to_search_for > numArray[middleIndex]){
        low = middleIndex + 1;
    }
  }
  
  return -1;
}

//---------------------------------------------------------------------------
long start = System.nanoTime();
for(int i =0; i<100; i++){            
    binarySearch(binarySearchTester, binarySearchTester[randomKey[i]]);
}
long finish = System.nanoTime();
long timeElapsed = finish - start;
System.out.println();
System.out.println("Nanoseconds: " + timeElapsed);

Nanoseconds: 14169391
Binary Search vs HashMap Lookup Time to Search
HashMap Lookup 12075520.2 ( 0.01207552 sec )
Binary Search 16676540 ( 0.01667654 sec )

  • Result: HashMap Lookup is faster than Binary Search

  • Reason: Because Hash algorithms are O(1) while binary search is O(log n).