Sort Notes
ChatGPT didn't help fr
- Queue Base Code
- Generic Class
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Tester Method for all sorters
- Data Object with Comparable
- Final Determination on best sort (with large array size)
- HashMap vs Binary Search
/**
* Implementation of a Double Linked List; forward and backward links point to adjacent Nodes.
*
*/
public class LinkedList<T>
{
private T data;
private LinkedList<T> prevNode, nextNode;
/**
* Constructs a new element
*
* @param data, data of object
* @param node, previous node
*/
public LinkedList(T data, LinkedList<T> node)
{
this.setData(data);
this.setPrevNode(node);
this.setNextNode(null);
}
/**
* Clone an object,
*
* @param node object to clone
*/
public LinkedList(LinkedList<T> node)
{
this.setData(node.data);
this.setPrevNode(node.prevNode);
this.setNextNode(node.nextNode);
}
/**
* Setter for T data in DoubleLinkedNode object
*
* @param data, update data of object
*/
public void setData(T data)
{
this.data = data;
}
/**
* Returns T data for this element
*
* @return data associated with object
*/
public T getData()
{
return this.data;
}
/**
* Setter for prevNode in DoubleLinkedNode object
*
* @param node, prevNode to current Object
*/
public void setPrevNode(LinkedList<T> node)
{
this.prevNode = node;
}
/**
* Setter for nextNode in DoubleLinkedNode object
*
* @param node, nextNode to current Object
*/
public void setNextNode(LinkedList<T> node)
{
this.nextNode = node;
}
/**
* Returns reference to previous object in list
*
* @return the previous object in the list
*/
public LinkedList<T> getPrevious()
{
return this.prevNode;
}
/**
* Returns reference to next object in list
*
* @return the next object in the list
*/
public LinkedList<T> getNext()
{
return this.nextNode;
}
}
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
LinkedList<T> head = null, tail = null;
/**
* Add a new object at the end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) // initial condition
this.head = this.tail = tail;
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
tail.setPrevNode(this.tail);
this.tail = tail; // update tail
}
}
public void addList(T[] lists) {
for (T data : lists) {
this.add(data);
}
}
/**
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
T data = this.peek();
if (this.tail != null) { // initial condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
}
return data;
}
/**
* Returns the data of head.
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
return this.head.getData();
}
/**
* Returns the head object.
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
/**
* Returns the tail object.
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
/**
* Returns the iterator object.
*
* @return this, instance of object
*/
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
/**
* Returns if queue is empty
*
* @return boolean if it is empty
*/
public boolean isEmpty() {
return this.head == null;
}
/**
* Changes the head
*
*/
public void setHead(LinkedList<T> h) {
this.head = h;
}
/**
* Returns size of queue
*
* @return size of queue
*/
public int size() {
int sz = 0;
for (T e: this) {
sz++;
}
return sz;
}
public String toString() {
int count = 0;
String str = "";
for (T e : this) {
str += e + " ";
count++;
}
return "count: " + count + ", data: " + str;
}
}
import java.util.*;
abstract class Sorter<T> {
String name;
long startTime;
long endTime;
long operations;
long compares;
long swaps;
public Sorter(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
abstract public Queue<T> sort(Queue<T> list, boolean verbose);
public Queue<T> sort(Queue<T> list) {
return this.sort(list, true);
}
public void start() {
this.startTime = (long) System.nanoTime();
}
public void stop() {
this.endTime = (long) System.nanoTime();
}
public long getElapsedTime() {
return this.endTime - this.startTime;
}
public long getOperations() {
return this.operations;
}
public long getCompares() {
return this.compares;
}
public long getSwaps() {
return this.swaps;
}
public void incrementCompares() {
this.compares++;
}
public void incrementSwaps() {
this.swaps++;
}
public void incrementOperations() {
this.operations++;
}
}
Bubble Sort
Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
It's time complexity is quite high, as it has to go through the entire array multiple times, constantly swapping elements and checking.
shown above is a rudimentary example of the steps that bubble sort takes to sort an array.
class BubbleSorter<T extends Comparable<T>> extends Sorter<T> {
public BubbleSorter() {
super("Bubble Sort");
}
public Queue<T> sort (Queue<T> q, boolean verbose) {
super.start();
boolean swapped = true;
LinkedList<T> head = q.getHead();
while (swapped) {
swapped = false;
LinkedList<T> current = head;
while (current.getNext() != null) {
if (current.getData().compareTo(current.getNext().getData()) > 0) {
T temp = current.getNext().getData();
current.getNext().setData(current.getData());
current.setData(temp);
swapped = true;
super.incrementSwaps();
}
super.incrementCompares();
current = current.getNext();
}
if (verbose) System.out.println("Intermediate: " + q);
}
super.stop();
return q;
}
}
Selection Sort
Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from an unsorted part of an array and swapping it with the first element of the unsorted part. This process is repeated until the entire array is sorted.
Here are the steps to perform a selection sort on an array of n elements:
- Set the first element as the minimum.
- Iterate through the remaining elements and compare each element with the current minimum.
- If a smaller element is found, set it as the new minimum.
- Once the end of the array is reached, swap the current minimum with the first element of the unsorted part.
- Increment the starting index of the unsorted part and repeat the above steps until the entire array is sorted.
Time complexity: O(n^2) (worst case)
class SelectionSorter<T extends Comparable<T>> extends Sorter<T> {
public SelectionSorter() {
super("Selection Sort");
}
public Queue<T> sort (Queue<T> q, boolean verbose) {
super.start();
LinkedList<T> current = q.getHead();
while (current.getNext() != null) {
LinkedList<T> lowest = current;
LinkedList<T> current2 = current.getNext();
while (current2 != null) {
if (lowest.getData().compareTo(current2.getData()) > 0) {
lowest = current2;
}
super.incrementCompares();
current2 = current2.getNext();
}
T temp = lowest.getData();
lowest.setData(current.getData());
current.setData(temp);
super.incrementSwaps();
if (verbose) System.out.println("Intermediate: " + q);
current = current.getNext();
}
super.stop();
return q;
}
}
Insertion Sort
Insertion sort is a simple sorting algorithm that works by iterating through an array of elements, comparing each element to the ones that came before it, and swapping them if they are out of order. This process is repeated until the entire array is sorted. It h as two parts: the sorted part and the unsorted part. The sorted part is at the beginning of the array, and the unsorted part is at the end of the array. The algorithm iterates through the unsorted part, removing one element at a time, and inserting it into the correct position in the sorted part. To insert, the algorithm compares elements to the sorted subaray from right to left. If the element is smaller than the current, the current element is shifted right. This process is repeated until the element is larger than the current element, or the beginning of the array is reached.
Time complexity: O(n^2) (worst case), but it can be better if the array is partially sorted. This makes it more efficient than selection sort and bubble sort, as those require going through the array the whole time.
class InsertionSorter<T extends Comparable<T>> extends Sorter<T> {
public InsertionSorter() {
super("Insertion Sort");
}
public Queue<T> sort (Queue<T> q, boolean verbose) {
super.start();
LinkedList<T> current = q.getHead().getNext();
while (current != null) {
LinkedList<T> next = current.getNext();
LinkedList<T> compared = current;
while (compared.getPrevious() != null && current.getData().compareTo(compared.getPrevious().getData()) < 0) {
compared = compared.getPrevious();
super.incrementCompares();
}
if (compared != current) {
if (current.getPrevious() != null) current.getPrevious().setNextNode(current.getNext());
if (current.getNext() != null) current.getNext().setPrevNode(current.getPrevious());
current.setNextNode(compared);
current.setPrevNode(compared.getPrevious());
if (compared.getPrevious() != null) compared.getPrevious().setNextNode(current);
compared.setPrevNode(current);
super.incrementSwaps();
if (current.getPrevious() == null) q.setHead(current);
}
current = next;
if (verbose) System.out.println("Intermediate: " + q);
}
super.stop();
return q;
}
}
Merge Sort
Merge sort is a divide and conquer algorithm that works by recursively splitting the array into two halves, sorting each half, and then merging the two sorted halves. The merge step is the most important part of the algorithm, as it is where the actual sorting takes place. The merge step works by comparing the first element of each half, and placing the smaller element into the result array. This process is repeated until all the elements have been placed into the result array.
Time complexity: O(nlogn) (worst case)
class MergeSorter<T extends Comparable<T>> extends Sorter<T> {
public MergeSorter() {
super("Merge Sort");
}
public Queue<T> sort (Queue<T> q, boolean verbose) {
super.start();
Queue<T> ret = sortFunc(q, verbose);
super.stop();
return ret;
}
public Queue<T> sortFunc (Queue<T> q, boolean verbose) {
if (q.size() == 1) return q;
List<Queue<T>> queues = splitQ(q);
Queue<T> ret = mergeQ(sort(queues.get(0), verbose), sort(queues.get(1), verbose));
if (verbose) System.out.println("Intermediate: " + ret);
return ret;
}
private Queue<T> mergeQ (Queue<T> firstQ, Queue<T> secondQ) {
Queue<T> mergedQ = new Queue<>();
while (!firstQ.isEmpty() || !secondQ.isEmpty()) {
if (firstQ.isEmpty()) {
mergedQ.add(secondQ.delete());
super.incrementSwaps();
}
else if (secondQ.isEmpty()) {
mergedQ.add(firstQ.delete());
super.incrementSwaps();
}
else if (firstQ.peek().compareTo(secondQ.peek()) <= 0) {
mergedQ.add(firstQ.delete());
super.incrementCompares();
super.incrementSwaps();
}
else {
mergedQ.add(secondQ.delete());
super.incrementSwaps();
super.incrementCompares();
}
}
return mergedQ;
}
private List<Queue<T>> splitQ (Queue<T> q) {
int end = q.size()/2 - 1;
int cnt = 0;
Queue<T> firstQ = new Queue<>();
Queue<T> secondQ = new Queue<>();
for (T i : q) {
if (cnt <= end) firstQ.add(i);
else secondQ.add(i);
super.incrementSwaps();
cnt++;
}
return List.of(firstQ, secondQ);
}
}
public class SortTester {
public static void main (String[] args) {
List<Sorter<Integer>> sorters = new ArrayList<Sorter<Integer>>();
sorters.add(new InsertionSorter<>());
sorters.add(new BubbleSorter<>());
sorters.add(new SelectionSorter<>());
sorters.add(new MergeSorter<>());
Integer[] arr = {10, 1, 3, 2, 5};
for (Sorter i : sorters) {
Queue<Integer> q = new Queue<>();
q.addList(arr);
System.out.println(i.getName());
System.out.println(i.sort(q));
System.out.println("Elapsed time: " + i.getElapsedTime() + "ns");
System.out.println("Number of compares: " + i.getCompares());
System.out.println("Number of swaps: " + i.getSwaps());
System.out.println();
}
System.out.println();
}
}
SortTester.main(null);
public class Person implements Comparable<Person> {
// Class data
public enum KeyType {name, email, passwordHash}
public static KeyType key = KeyType.name; // static initializer
public static void setOrder(KeyType key) {Person.key = key;}
// Instance data
private String name;
private String email;
private String passwordHash;
/* constructor
*
*/
public Person(String name, String email, String passwordHash)
{
this.name = name;
this.email = email;
this.passwordHash = passwordHash;
}
protected KeyType getKey() { return Person.key; }
// compare
@Override
public int compareTo(Person obj) {
if (this.key == KeyType.name) return this.name.compareTo(obj.name);
else if (this.key == KeyType.email) return this.email.compareTo(obj.email);
else if (this.key == KeyType.passwordHash) return this.passwordHash.compareTo(obj.passwordHash);
else return 0;
}
public String getName() { return name; }
public String getEmail() { return email; }
public String getPasswordHash() { return passwordHash; }
public String toString()
{
return "{ \"Name\": \"" + name + "\", \"Email\": \"" + email + "\", \"Password\": \"" + passwordHash + "\" }";
}
// Test data initializer
public static Person[] persons()
{
return new Person[] {
new Person("John", "1john@email.com", "password"),
new Person("Mary", "mary@email.com", "password2"),
new Person("Bob", "bob@email.com", "password3"),
new Person("Alice", "alice@email.com", "dfsefa"),
new Person("Zoe", "bruh@gmail.com", "deawea"),
new Person("Frank", "uniqlo@mail.com", "ewaksjd")
};
}
/* main to test Person class
*
*/
public static void main(String[] args)
{
// Inheritance Hierarchy
//Person[] objs = persons();
Person john = new Person("John", "1john@email.com", "password");
Person mary = new Person("Mary", "funmary@email.com", "password2");
// print with title
System.out.println("Person Class Test");
System.out.println(john.toString());
System.out.println("Compare John to Mary: passwordHash");
Person.setOrder(KeyType.passwordHash);
System.out.println(john.compareTo(mary));
System.out.println("Compare John to Mary: name");
Person.setOrder(KeyType.name);
System.out.println(john.compareTo(mary));
System.out.println("Compare John to Mary: email");
Person.setOrder(KeyType.email);
System.out.println(john.compareTo(mary));
}
}
Person.main(null);
public class SortTesterPerson {
public static void main (String[] args) {
List<Sorter<Person>> sorters = new ArrayList<Sorter<Person>>();
sorters.add(new InsertionSorter<>());
sorters.add(new BubbleSorter<>());
sorters.add(new SelectionSorter<>());
sorters.add(new MergeSorter<>());
Person[] arr = Person.persons();
Person.setOrder(Person.KeyType.email);
for (Sorter i : sorters) {
Queue<Person> q = new Queue<>();
q.addList(arr);
System.out.println(i.getName());
System.out.println(i.sort(q));
System.out.println("Elapsed time: " + i.getElapsedTime() + "ns");
System.out.println("Number of compares: " + i.getCompares());
System.out.println("Number of swaps: " + i.getSwaps());
}
System.out.println();
}
}
SortTesterPerson.main(null);
class Analytics {
private List<Long> times = new ArrayList<>();
private List<Long> ops = new ArrayList<>();
private List<Long> compares = new ArrayList<>();
private List<Long> swaps = new ArrayList<>();
public void addTime (long time) {
times.add(time);
}
public double getAvgTime () {
Collections.sort(times);
long tot = 0;
long cnt = 0;
for (int i = 1; i<times.size()-1; i++) {
tot += times.get(i);
cnt++;
}
if (cnt == 0) return 0;
return (double)tot/(double)cnt;
}
public void addOps (long op) {
ops.add(op);
}
public void addCompares (long comp) {
compares.add(comp);
}
public void addSwaps (long swap) {
swaps.add(swap);
}
public double getAvgOps () {
Collections.sort(ops);
long tot = 0;
long cnt = 0;
for (int i = 1; i<ops.size()-1; i++) {
tot += ops.get(i);
cnt++;
}
if (cnt == 0) return 0;
return (double)tot/(double)cnt;
}
public double getAvgCompares () {
Collections.sort(compares);
long tot = 0;
long cnt = 0;
for (int i = 1; i<compares.size()-1; i++) {
tot += compares.get(i);
cnt++;
}
if (cnt == 0) return 0;
return (double)tot/(double)cnt;
}
public double getAvgSwaps () {
Collections.sort(swaps);
long tot = 0;
long cnt = 0;
for (int i = 1; i<swaps.size()-1; i++) {
tot += swaps.get(i);
cnt++;
}
if (cnt == 0) return 0;
return (double)tot/(double)cnt;
}
}
public class SortTester {
public static void main (String[] args) {
List<Sorter<Integer>> sorters = new ArrayList<Sorter<Integer>>();
sorters.add(new InsertionSorter<>());
sorters.add(new BubbleSorter<>());
sorters.add(new SelectionSorter<>());
sorters.add(new MergeSorter<>());
HashMap<String, Analytics> analytics = new HashMap<>();
for (Sorter i : sorters) analytics.put(i.getName(), new Analytics());
for (int i = 0; i<12; i++) {
Integer[] arr = new Integer[5000];
for (int j = 0; j<5000; j++) {
arr[j] = (int)(10000 * Math.random());
}
for (Sorter s : sorters) {
Queue<Integer> q = new Queue<>();
q.addList(arr);
s.sort(q, false);
analytics.get(s.getName()).addTime(s.getElapsedTime());
analytics.get(s.getName()).addCompares(s.getCompares());
analytics.get(s.getName()).addSwaps(s.getSwaps());
}
}
for (Sorter i : sorters) {
System.out.println(i.getName());
System.out.println("Average Time (High/Low excluded): " + analytics.get(i.getName()).getAvgTime() + "ns");
System.out.println("Average Compares (High/Low excluded): " + analytics.get(i.getName()).getAvgCompares());
System.out.println("Average Swaps (High/Low excluded): " + analytics.get(i.getName()).getAvgSwaps());
System.out.println();
}
}
}
SortTester.main(null);
We can determine the best sort is merge sort due to its much lower operations and elapsed time. This is supported by the fact its time complexity is O(n*logn) while the other sorts are O(n^2)
Furthermore, merge sort also has the least number of average compares by a long shot, and although the swaps are not as low as the other sorts, this is just due to the amount of data that is being added into the array one by one. I counted each as a "swap", even though they're not really swaps.
public class HashVsBinary {
private static List<Long> hashTimes = new ArrayList<>();
private static List<Long> binaryTimes = new ArrayList<>();
public double getAvgTime (List<Long> times) {
Collections.sort(times);
long tot = 0;
long cnt = 0;
for (int i = 1; i<times.size()-1; i++) {
tot += times.get(i);
cnt++;
}
if (cnt == 0) return 0;
return (double)tot/(double)cnt;
}
public Person binarySearch (ArrayList<Integer> keys, ArrayList<Person> values, int key) {
int low = 0;
int high = keys.size()-1;
while (low <= high) {
int mid = (low + high) / 2;
if (keys.get(mid) < key) {
low = mid + 1;
} else if (keys.get(mid) > key) {
high = mid - 1;
} else {
return values.get(mid);
}
}
return null;
}
public static void main(String[] args) {
for (int i = 0; i<12; i++) {
HashMap<Integer, Person> map = new HashMap<>();
ArrayList<Integer> keys = new ArrayList<>();
ArrayList<Person> values = new ArrayList<>();
for (int j = 0; j<5000; j++) {
String name = Double.toString(Math.random() * 1000000);
String email = Double.toString(Math.random() * 1000000);
String password = Double.toString(Math.random() * 1000000);
Person p = new Person(name, email, password);
map.put(j, p);
keys.add(j);
values.add(p);
}
for (int j = 0; j<100; j++) {
int key = (int)(Math.random() * 5000);
long start = System.nanoTime();
map.get(key);
long end = System.nanoTime();
long hashTime = end - start;
hashTimes.add(hashTime);
long start2 = System.nanoTime();
new HashVsBinary().binarySearch(keys, values, key);
long end2 = System.nanoTime();
long binaryTime = end2 - start2;
binaryTimes.add(binaryTime);
}
}
System.out.println("Average Time Hash (High/Low excluded): " + new HashVsBinary().getAvgTime(hashTimes) + "ns");
System.out.println("Average Time Binary (High/Low excluded): " + new HashVsBinary().getAvgTime(binaryTimes) + "ns");
}
}
HashVsBinary.main(null);
| HashMap | Binary Search | |
|---|---|---|
| Worst Case | O(n) | O(logn) |
| Best Case | O(1) | O(1) |
| Average Case | O(1) | O(logn) |