Sorting Algorithm's

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Big O analysis
  • Conclusion
• Sorting
• Hashmaps

Bubble Sort

• Very simple
• Goes through each element and compares to adjacent elements and switches if
• High time complexity
  • O(n^2)

public class BubbleSort{
    public static void main(String[] args){
        int[] list = new int[5000];
        for (int i = 0; i < list.length; i++) {
            list[i] = (int) (Math.random() * 5000);
        }

        int tmp = 0;

        System.out.println("Unsorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        System.out.println(" ");

        long startTime = System.nanoTime();
        for (int i = 0; i < list.length; i++){
            for (int j = 1; j < (list.length - i); j++){
                if (list[j - 1] > list[j]){
                    tmp = list[j-1];
                    list[j-1] = list[j];
                    list[j] = tmp;
                }
            }
        }
        System.out.println("Sorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        long endTime   = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println("");
        System.out.println("Runtime: ");
        System.out.println(totalTime + " nanoseconds");
    }
}
BubbleSort.main(null);

Selection Sort

• Goes value by value through entire list and looks for the smallest value
• Swaps positions with that value
• Goes through each value and checks each value
• O(n^2) time complexity

public class SelectionSort{
    public static void main(String[] args){
        int[] list = new int[5000];
        for (int i = 0; i < list.length; i++) {
            list[i] = (int) (Math.random() * 5000);
        }

        int tmp = 0;

        System.out.println("Unsorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        System.out.println(" ");

        long startTime = System.nanoTime();

        // Selection Sorting algorithm
        
        for (int i = 0; i < list.length - 1; i++){
            int index = i;
            for (int j = i + 1; j < list.length; j++){
                if (list[j] < list[index]){
                    index = j;
                }
            }
            tmp = list[index];
            list[index] = list[i];
            list[i] = tmp;
        }

        // End of Selection Sorting algorithm
        // Printing the sorted listay

        System.out.println("Sorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        long endTime   = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println("");
        System.out.println("Runtime: ");
        System.out.println(totalTime + " nanoseconds");
    }
}
SelectionSort.main(null);

Insertion Sort

• Linear algorithm
• Goes through each element and looks if next element is less than it
• If so, swaps
• O(n^2) time complexity

public class InsertionSort{
    public static void main(String[] args){
        int[] list = new int[5000];
        for (int i = 0; i < list.length; i++) {
            list[i] = (int) (Math.random() * 5000);
        }

        int tmp = 0;

        System.out.println("Unsorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        System.out.println(" ");

        long startTime = System.nanoTime();

        // Insertion Sorting algorithm
        
        for (int i = 1; i < list.length; i++){
            int tmp = list[i];
            int j = i - 1;
            while (j >= 0 && list[j] > tmp){
                list[j + 1] = list[j];
                j = j - 1;
            }
            list[j + 1] = tmp;
        }

        // End of Insertion Sorting algorithm
        // Printing the sorted listay

        System.out.println("Sorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        long endTime   = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println("");
        System.out.println("Runtime: ");
        System.out.println(totalTime + " nanoseconds");
    }
}
InsertionSort.main(null);

Merge Sort

• Splits array in half over and over again until the values can be compared
• Then swaps if needed
• O(n*log(n))

public class MergeSort{
    public static void mergeSort(int[] list, int n) {
        if (n < 2) {
            return;
        }
        int midVal = n / 2;
        int[] l = new int[midVal];
        int[] r = new int[n - midVal];

        for (int i = 0; i < midVal; i++) {
            l[i] = list[i];
        }
        for (int i = midVal; i < n; i++) {
            r[i - midVal] = list[i];
        }
        mergeSort(l, midVal);
        mergeSort(r, n - midVal);

        merge(list, l, r, midVal, n - midVal);
    }

    public static void merge(
    int[] list, int[] l, int[] r, int left, int right) {
    
        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                list[k++] = l[i++];
            }
            else {
                list[k++] = r[j++];
            }
        }
        while (i < left) {
            list[k++] = l[i++];
        }
        while (j < right) {
            list[k++] = r[j++];
        }
    }


    public static void main(String[] args){
        int[] list = new int[5000];
        for (int i = 0; i < list.length; i++) {
            list[i] = (int) (Math.random() * 10000);
        }

        int tmp = 0;

        System.out.println("Unsorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        System.out.println(" ");

        long startTime = System.nanoTime();

        // Merge Sorting algorithm
        
        mergeSort(list, list.length);

        // End of Merge Sorting algorithm
        // Printing the sorted list

        System.out.println("Sorted:");
        for(int i = 0; i < list.length; i++){
            System.out.print(list[i] + " ");
        }
        long endTime   = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println("");
        System.out.println("Runtime: ");
        System.out.println(totalTime + " nanoseconds");
    }
}
MergeSort.main(null);

Big O analysis

• Fastest is merge sort
• 2nd fastest is selection sort
• 3rd fastest is insertion sort
• 4th fastest is bubble sort

Conclusion

• The fastest algorithm is merge sort
  • Makes sense as it has list O(n*log(n)) time complexity
• Slowest is bubble sort
  • Has list O(n^2) time complexity making it inefficient in comparison

Sorting

public class SortLists{
    // initializing the list of 5000 elements
    public static int[] createList() {
        int[] list = new int[5000];
        for (int i = 0; i < list.length; i++) {
            list[i] = (int) (Math.random() * 10000);
        }
        return list;
    }

    // bubble sorting algorithm
    public static void bubbleSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            for (int j = 0; j < list.length - 1 - i; j++) {
                if (list[j] > list[j + 1]) {
                    int tmp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = tmp;
                }
            }
        }
    }

    // selection sorting algorithm
    public static void selectionSort(int[] list) {
        for (int i = 0; i < list.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = list[i];
            list[i] = list[minIndex];
            list[minIndex] = tmp;
        }
    }

    // insertion sorting algorithm
    public static void insertionSort(int[] list) {
        for (int i = 1; i < list.length; i++) {
            int current = list[i];
            int j = i - 1;
            while (j >= 0 && current < list[j]) {
                list[j + 1] = list[j];
                j--;
            }
            list[j + 1] = current;
        }
    }
    
    // merge sorting algorithm
    public static void mergeSort(int[] list) {
        if (list.length > 1) {
            int[] left = leftHalf(list);
            int[] right = rightHalf(list);

            mergeSort(left);
            mergeSort(right);

            merge(list, left, right);
        }
    }
    public static int[] rightHalf(int[] list) {
        int size1 = list.length / 2;
        int size2 = list.length - size1;
        int[] right = new int[size2];
        for (int i = 0; i < size2; i++) {
            right[i] = list[i + size1];
        }
        return right;
    }
    public static int[] leftHalf(int[] list) {
        int size1 = list.length / 2;
        int[] left = new int[size1];
        for (int i = 0; i < size1; i++) {
            left[i] = list[i];
        }
        return left;
    }
    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;
    }

    // tester method to test the sorting algorithms
    public static void main(String[] args){
        // initializing the array of 5000 elements
        int[] list = createList();

        // bubble sort runtimes check
        long startTime = System.nanoTime();
        bubbleSort(list);
        long endTime   = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println("Bubble Sort Runtime: ");
        System.out.println(totalTime + " nanoseconds");
        System.out.println(" ");

        // insertion sort runtimes check
        startTime = System.nanoTime();
        insertionSort(list);
        endTime   = System.nanoTime();
        totalTime = endTime - startTime;
        System.out.println("Insertion Sort Runtime: ");
        System.out.println(totalTime + " nanoseconds");
        System.out.println(" ");

        // selection sort runtimes check
        startTime = System.nanoTime();
        selectionSort(list);
        endTime   = System.nanoTime();
        totalTime = endTime - startTime;
        System.out.println("Selection Sort Runtime: ");
        System.out.println(totalTime + " nanoseconds");
        System.out.println(" ");

        // merge sort runtimes check
        startTime = System.nanoTime();
        mergeSort(list);
        endTime   = System.nanoTime();
        totalTime = endTime - startTime;
        System.out.println("Merge Sort Runtime: ");
        System.out.println(totalTime + " nanoseconds");
        System.out.println(" ");
    }
}
SortLists.main(null);

Hashmaps

import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;

public class Hash {
    public static void main(String[] args){
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
        int[] list = new int[5000];

        for (int i = 0; i < list.length; i++) {
            Integer value = (int) (Math.random() * 5000);
            hashmap.put(value, value);
            list[i] = value;
        }

        long lookUpTime = (lookUp(hashmap, 12));
        System.out.println("Look up time: " + lookUpTime + " nanoseconds");
        long binarySearchTime = (binarySearchTime(list, 12));
        System.out.println("Binary search time: " + binarySearchTime + " nanoseconds");
        
    }

    public static long lookUp(HashMap<Integer, Integer> hashmap, Integer value) {
        long start = System.nanoTime();
        hashmap.containsKey(value);
        long end = System.nanoTime();
        return (end - start);
    }

    public static long binarySearchTime(int[] list, Integer value) {
        long start = System.nanoTime();
        // binary search 
        int low = 0;
        int high = list.length - 1;
        int middle = (low + high) / 2;
        while (low <= high) {
            if (list[middle] < value) {
                low = middle + 1;
            } else if (list[middle] == value) {
                break;
            } else {
                high = middle - 1;
            }
            middle = (low + high) / 2;
        }
        long end = System.nanoTime();
        return (end - start);
    }
}
Hash.main(null);