Sort

• Hasmap vs Binary Search lookup

public class MyLinkedList<T> {
    private T data;
    private MyLinkedList<T> prev, next;

    public MyLinkedList(T data, MyLinkedList<T> prev) {
        this.data = data;
        this.prev = prev;
        this.next = null;
    }

    public MyLinkedList(MyLinkedList<T> node) {
        this.data = node.data;
        this.prev = node.prev;
        this.next = node.next;
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setPrev(MyLinkedList<T> prev) {
        this.prev = prev;
    }

    public void setNext(MyLinkedList<T> next) {
        this.next = next;
    }

    public MyLinkedList<T> getPrev() {
        return prev;
    }

    public MyLinkedList<T> getNext() {
        return next;
    }
}

public class MyStack<T> {
    private MyLinkedList<T> top;
    private int size;

    public MyStack() {
        top = null;
        size = 0;
    }

    public void push(T data) {
        MyLinkedList<T> newNode = new MyLinkedList<>(data, top);
        top = newNode;
        size++;
    }

    public T peek() {
        if (top == null) {
            System.out.println("Empty stack!");
            return null;
        }
        return top.getData();
    }

    public T pop() {
        if (top == null) {
            System.out.println("Empty stack!");
            return null;
        }
        T data = top.getData();
        top = top.getPrev();
        size--;
        return data;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");
        MyLinkedList<T> currentNode = top;
        while (currentNode != null) {
            sb.append(currentNode.getData());
            currentNode = currentNode.getPrev();
            if (currentNode != null) {
                sb.append(", ");
            }
        }
        sb.append(" ]");
        return sb.toString();
    }

    public void bubbleSort() {
        if (size <= 1) {
            return;
        }
        MyStack<T> sorted = new MyStack<>();
        while (!isEmpty()) {
            T temp = pop();
            while (!sorted.isEmpty() && ((Comparable<T>) sorted.peek()).compareTo(temp) > 0) {
                push(sorted.pop());
            }
            sorted.push(temp);
        }
        while (!sorted.isEmpty()) {
            push(sorted.pop());
        }
    }

    public void selectionSort() {
        if (size <= 1) {
            return;
        }
        MyStack<T> sorted = new MyStack<>();
        while (!isEmpty()) {
            T temp = pop();
            while (!sorted.isEmpty() && ((Comparable<T>) sorted.peek()).compareTo(temp) > 0) {
                push(sorted.pop());
            }
            sorted.push(temp);
        }
        while (!sorted.isEmpty()) {
            push(sorted.pop());
        }
    }


    public void mergeSort() {
        top = mergeSort(top);
    }
    
    private MyLinkedList<T> mergeSort(MyLinkedList<T> head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        MyLinkedList<T> mid = getMid(head);
        MyLinkedList<T> nextToMid = mid.getNext();
        mid.setNext(null);
        MyLinkedList<T> left = mergeSort(head);
        MyLinkedList<T> right = mergeSort(nextToMid);
        return merge(left, right);
    }
    
    private MyLinkedList<T> merge(MyLinkedList<T> left, MyLinkedList<T> right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        MyLinkedList<T> result;
        if (((Comparable<T>) left.getData()).compareTo(right.getData()) <= 0) {
            result = left;
            result.setNext(merge(left.getNext(), right));
        } else {
            result = right;
            result.setNext(merge(left, right.getNext()));
        }
        return result;
    }
    
    private MyLinkedList<T> getMid(MyLinkedList<T> head) {
        if (head == null) {
            return head;
        }
        MyLinkedList<T> slow = head;
        MyLinkedList<T> fast = head.getNext();
        while (fast != null) {
            fast = fast.getNext();
            if (fast != null) {
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }    
    
    
    public void insertionSort() {
        if (size <= 1) {
            return;
        }
        MyStack<T> sorted = new MyStack<>();
        sorted.push(pop());
    
        while (!isEmpty()) {
            T current = pop();
            if (((Comparable<T>) current).compareTo(sorted.peek()) > 0) {
                sorted.push(current);
            } else {
                while (!sorted.isEmpty() && ((Comparable<T>) sorted.peek()).compareTo(current) > 0) {
                    push(sorted.pop());
                }
                sorted.push(current);
            }
        }
    
        while (!sorted.isEmpty()) {
            push(sorted.pop());
        }
    }
}

public class Tester {
public static void main(String[] args) {
    MyStack<Integer> stack = new MyStack<>();
    stack.push(5);
    stack.push(2);
    stack.push(9);
    stack.push(1);
    stack.push(7);
    stack.push(3);
    System.out.println("Original stack: " + stack);
    
    // Testing bubble sort
    stack.bubbleSort();
    System.out.println("Stack after bubble sort: " + stack);
    
    // Testing selection sort
    stack.selectionSort();
    System.out.println("Stack after selection sort: " + stack);

    // Testing merge sort
    stack.mergeSort();
    System.out.println("Stack after merge sort: " + stack);

    // Testing insertion sort
    stack.insertionSort();
    System.out.println("Stack after insertion sort: " + stack);
}
}

Tester.main(null);

Original stack: [ 3, 7, 1, 9, 2, 5 ]
Stack after bubble sort: [ 1, 2, 3, 5, 7, 9 ]
Stack after selection sort: [ 1, 2, 3, 5, 7, 9 ]
Stack after merge sort: [ 1, 2, 3, 5, 7, 9 ]
Stack after insertion sort: [ 1, 2, 3, 5, 7, 9 ]

import java.util.Random;

public class BigO {
    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        Random rand = new Random();

        // push 500 random elements to the stack
        for (int i = 0; i < 5; i++) {
            stack.push(rand.nextInt(5));
        }

        // time bubble sort
        long start = System.nanoTime();
        stack.bubbleSort();
        long end = System.nanoTime();
        long bubbleSortTime = end - start;

        // time selection sort
        start = System.nanoTime();
        stack.selectionSort();
        end = System.nanoTime();
        long selectionSortTime = end - start;

        // time merge sort
        start = System.nanoTime();
        stack.mergeSort();
        end = System.nanoTime();
        long mergeSortTime = end - start;

        // time insertion sort
        start = System.nanoTime();
        stack.insertionSort();
        end = System.nanoTime();
        long insertionSortTime = end - start;

        // print the times for each sorting method
        System.out.println("Bubble sort time: " + bubbleSortTime + " ns");
        System.out.println("Selection sort time: " + selectionSortTime + " ns");
        System.out.println("Merge sort time: " + mergeSortTime + " ns");
        System.out.println("Insertion sort time: " + insertionSortTime + " ns");
    }
}
BigO.main(null);

Bubble sort time: 7100 ns
Selection sort time: 1400 ns
Merge sort time: 1500 ns
Insertion sort time: 1800 ns

import java.util.Random;

public class BigO {
    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        Random rand = new Random();

        // push 500 random elements to the stack
        for (int i = 0; i < 5000; i++) {
            stack.push(rand.nextInt(5000));
        }

        // time bubble sort
        long start = System.nanoTime();
        stack.bubbleSort();
        long end = System.nanoTime();
        long bubbleSortTime = end - start;

        // time selection sort
        start = System.nanoTime();
        stack.selectionSort();
        end = System.nanoTime();
        long selectionSortTime = end - start;

        // time merge sort
        start = System.nanoTime();
        stack.mergeSort();
        end = System.nanoTime();
        long mergeSortTime = end - start;

        // time insertion sort
        start = System.nanoTime();
        stack.insertionSort();
        end = System.nanoTime();
        long insertionSortTime = end - start;

        // print the times for each sorting method
        System.out.println("Bubble sort time: " + bubbleSortTime + " ns");
        System.out.println("Selection sort time: " + selectionSortTime + " ns");
        System.out.println("Merge sort time: " + mergeSortTime + " ns");
        System.out.println("Insertion sort time: " + insertionSortTime + " ns");
    }
}
BigO.main(null);

Bubble sort time: 137113100 ns
Selection sort time: 695700 ns
Merge sort time: 4600 ns
Insertion sort time: 700600 ns

Aspect	Collection	Hash Map
Pros	Provides methods for working with groups of objects	Provides faster access and search, Thread safe synchronization
	Ordered and sorted collections are available	Efficient for large datasets, supports null values
	Implements Iterable interface	Key-value pairs
Cons	Slower access and search for large datasets	Not ordered
	No direct way to access items by key	More complex and requires additional operations for iterating over the elements
	Does not support key-value pairs

Hasmap vs Binary Search lookup

// imports random class
import java.util.Random;

public class TimeCompare {
    private HashMap<Integer, Integer> hashmap;
    private int[] keys;

    // time comparison method
    public TimeCompare(int numRecords) {
        hashmap = new HashMap<>();
        keys = new int[numRecords];
        Random random = new Random();
        
        // for each key
        for (int i = 0; i < numRecords; i++) {
            int key = random.nextInt(numRecords);
            hashmap.put(key, i);
            keys[i] = key;
        }
    }

    // removes the first and last keys to eliminate outliers
    public int binarySearchLookup(int key) {
        int start = 0;
        int end = keys.length - 1;
        while (start <= end) {
            int middlekey = (start + end) / 2;
            if (keys[middlekey] == key) {
                return hashmap.get(keys[middlekey]);
            } else if (keys[middlekey] < key) {
                start = middlekey + 1;
            } else {
                end = middlekey - 1;
            }
        }
        return -1;
    }

    public int hashmapLookup(int key) {
        return hashmap.getOrDefault(key, -1);
    }

    // 12 trials, 100 lookups, sets time for binarysearch and hashmap to 0
    public void runBenchmark() {
        int numTrials = 12;
        int numLookups = 100;
        long binarySearchTotalTime = 0;
        long hashmapTotalTime = 0;

        for (int i = 0; i < numTrials; i++) {
            // shuffle the keys array to get a random set of keys
            shuffleKeys();

            // perform binary search lookups
            long binarySearchStartTime = System.nanoTime();
            for (int j = 0; j < numLookups; j++) {
                int key = keys[j];
                binarySearchLookup(key);
            }
            long binarySearchEndTime = System.nanoTime();
            binarySearchTotalTime += binarySearchEndTime - binarySearchStartTime;

            // perform hashmap lookups
            long hashmapStartTime = System.nanoTime();
            for (int j = 0; j < numLookups; j++) {
                int key = keys[j];
                hashmapLookup(key);
            }
            long hashmapEndTime = System.nanoTime();
            hashmapTotalTime += hashmapEndTime - hashmapStartTime;
        }

        // Find averages
        long binarySearchAvgTime = binarySearchTotalTime / (numTrials * numLookups);
        long hashmapAvgTime = hashmapTotalTime / (numTrials * numLookups);

        System.out.println("Binary search avg = " + binarySearchAvgTime + " ns");
        System.out.println("Hashmap avg = " + hashmapAvgTime + " ns");
    }

    // Generate random keys
    private void shuffleKeys() {
        Random random = new Random();
        for (int i = keys.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int temp = keys[i];
            keys[i] = keys[j];
            keys[j] = temp;
        }
    }

    // runs for 5000 keys
    public static void main(String[] args) {
        TimeCompare timeCompare = new TimeCompare(5000);
        timeCompare.runBenchmark();
    }
}

TimeCompare.main(null);

Binary search avg = 347 ns
Hashmap avg = 438 ns