More Algorythmic - Actually Doing the Sorts • 23 min read

Class

import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
import java.util.Collections;

public class Beachgoer implements Comparable<Beachgoer>{
    private String name;
    private int length;

    // Constructor
    public Beachgoer(String name, int length) {
        this.name = name;
        this.length = length;
    }

    // Getter methods
    public String getName() {
        return name;
    }

    public int getLength() {
        return length;
    }

    @Override
    public int compareTo(Beachgoer other) {
        return Integer.compare(this.length, other.length);
    }

    public static ArrayList<Beachgoer> createList(){
        Beachgoer bg1 = new Beachgoer("Scuba Diver", 1);
        Beachgoer bg2 = new Beachgoer("Karen", 2);
        Beachgoer bg3 = new Beachgoer("Beatboxer", 3);
        Beachgoer bg4 = new Beachgoer("Corn Oil", 4);
        Beachgoer bg5 = new Beachgoer("Lifeguard", 5);
        Beachgoer bg6 = new Beachgoer("Runner", 6);
        Beachgoer bg7 = new Beachgoer("Rapper", 7);
        Beachgoer bg8 = new Beachgoer("Beach Volleyball Dude", 8);
        Beachgoer bg9 = new Beachgoer("M.A.T.I", 9);
        Beachgoer bg10 = new Beachgoer("Click, Half Dolphin, Half Man", 10);
        Beachgoer bg11 = new Beachgoer("Sandcastle", 11);
        Beachgoer bg12 = new Beachgoer("Beach Volleyball Dudette", 12);
        Beachgoer bg13 = new Beachgoer("Surfer", 13);

        // Creating a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = new ArrayList<Beachgoer>();
        beachgoerList.add(bg1);
        beachgoerList.add(bg2);
        beachgoerList.add(bg3);
        beachgoerList.add(bg4);
        beachgoerList.add(bg5);
        beachgoerList.add(bg6);
        beachgoerList.add(bg7);
        beachgoerList.add(bg8);
        beachgoerList.add(bg9);
        beachgoerList.add(bg10);
        beachgoerList.add(bg11);
        beachgoerList.add(bg12);
        beachgoerList.add(bg13);
        
        Collections.shuffle(beachgoerList);

        return beachgoerList;
    }

    public static ArrayList<Beachgoer> createShorterList(){
        Beachgoer bg1 = new Beachgoer("Scuba Diver", 1);
        Beachgoer bg2 = new Beachgoer("Karen", 2);
        Beachgoer bg3 = new Beachgoer("Beatboxer", 3);
        Beachgoer bg4 = new Beachgoer("Corn Oil", 4);
        Beachgoer bg5 = new Beachgoer("Lifeguard", 5);

        // Creating a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = new ArrayList<Beachgoer>();
        beachgoerList.add(bg1);
        beachgoerList.add(bg2);
        beachgoerList.add(bg3);
        beachgoerList.add(bg4);
        beachgoerList.add(bg5);
        
        Collections.shuffle(beachgoerList);

        return beachgoerList;
    }

    public static void main(String[] args) {
        // Creating objects of Beachgoer
        Beachgoer bg1 = new Beachgoer("Scuba Diver", 1);
        Beachgoer bg2 = new Beachgoer("Karen", 2);
        Beachgoer bg3 = new Beachgoer("Beatboxer", 3);
        Beachgoer bg4 = new Beachgoer("Corn Oil", 4);
        Beachgoer bg5 = new Beachgoer("Lifeguard", 5);
        Beachgoer bg6 = new Beachgoer("Runner", 6);
        Beachgoer bg7 = new Beachgoer("Rapper", 7);
        Beachgoer bg8 = new Beachgoer("Beach Volleyball Dude", 8);
        Beachgoer bg9 = new Beachgoer("M.A.T.I", 9);
        Beachgoer bg10 = new Beachgoer("Click, Half Dolphin, Half Man", 10);
        Beachgoer bg11 = new Beachgoer("Sandcastle", 11);
        Beachgoer bg12 = new Beachgoer("Beach Volleyball Dudette", 12);
        Beachgoer bg13 = new Beachgoer("Surfer", 13);

        // Creating a list of Beachgoer objects
        List<Beachgoer> beachgoerList = new ArrayList<Beachgoer>();
        beachgoerList.add(bg1);
        beachgoerList.add(bg2);
        beachgoerList.add(bg3);
        beachgoerList.add(bg4);
        beachgoerList.add(bg5);
        beachgoerList.add(bg6);
        beachgoerList.add(bg7);
        beachgoerList.add(bg8);
        beachgoerList.add(bg9);
        beachgoerList.add(bg10);
        beachgoerList.add(bg11);
        beachgoerList.add(bg12);
        beachgoerList.add(bg13);

        Iterator<Beachgoer> iterator = beachgoerList.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            i++;
            Beachgoer beachgoer = iterator.next();
            System.out.println("Name: " + beachgoer.getName());
            System.out.println("Length: " + beachgoer.getLength());
            System.out.println();
            if(i == 3){
                break;
            }
        }
    }
}

Beachgoer.main(null);

Name: Scuba Diver
Length: 1

Name: Karen
Length: 2

Name: Beatboxer
Length: 3

Using Linked Lists and Implementing

public class LinkedList<T extends Comparable<T>> {
    
    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    public LinkedList() {
        this.head = null;
    }

    public void add(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node lastNode = head;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }
        lastNode.next = newNode;
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void selectionSort() {
        if (head == null || head.next == null) {
            return;
        }
        Node current = head;
        while (current != null) {
            Node min = current;
            Node nextNode = current.next;
            while (nextNode != null) {
                if (nextNode.data.compareTo(min.data) < 0) {
                    min = nextNode;
                }
                nextNode = nextNode.next;
            }
            // Swap data between current node and min node
            if (min != current) {
                T temp = current.data;
                current.data = min.data;
                min.data = temp;
            }
            current = current.next;
        }
    }

    public void insertionSort() {
        if (head == null || head.next == null) {
            return;
        }
        Node sorted = null;
        Node current = head;
        while (current != null) {
            Node next = current.next;
            sorted = insertSorted(sorted, current);
            current = next;
        }
        head = sorted;
    }

    private Node insertSorted(Node sorted, Node newNode) {
        if (sorted == null || sorted.data.compareTo(newNode.data) >= 0) {
            newNode.next = sorted;
            sorted = newNode;
        } else {
            Node current = sorted;
            while (current.next != null && current.next.data.compareTo(newNode.data) < 0) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        return sorted;
    }

    public void bubbleSort() {
        if (head == null || head.next == null) {
            return;
        }
        boolean swapped;
        Node current;
        Node lastUnsorted = null;
        do {
            swapped = false;
            current = head;
            while (current.next != lastUnsorted) {
                if (current.data.compareTo(current.next.data) > 0) {
                    T temp = current.data;
                    current.data = current.next.data;
                    current.next.data = temp;
                    swapped = true;
                }
                current = current.next;
            }
            lastUnsorted = current;
        } while (swapped);
    }

    public void mergeSort() {
        head = mergeSortRec(head);
    }

    private Node mergeSortRec(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node middle = getMiddle(head);
        Node nextOfMiddle = middle.next;
        middle.next = null;
        Node left = mergeSortRec(head);
        Node right = mergeSortRec(nextOfMiddle);
        return sortedMerge(left, right);
    }

    private Node getMiddle(Node head) {
        if (head == null) {
            return head;
        }
        Node slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private Node sortedMerge(Node left, Node right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        Node result;
        if (left.data.compareTo(right.data) <= 0) {
            result = left;
            result.next = sortedMerge(left.next, right);
        } else {
            result = right;
            result.next = sortedMerge(left, right.next);
        }
        return result;
    }

    public static void main(String[] args) {
        // Example usage:
        // Creating a linked list of integers
        LinkedList<Integer> intList = new LinkedList<>();
        intList.add(3);
        intList.add(1);
        intList.add(2);
        System.out.println("Original list:");
        intList.display();

        intList.insertionSort();
        System.out.println("Sorted list using Insertion Sort:");
        intList.display();

        intList.add(3);
        intList.add(1);
        intList.add(2);
        intList.bubbleSort();
        System.out.println("Sorted list using Bubble Sort:");
        intList.display();

        intList.add(3);
        intList.add(1);
        intList.add(2);
        intList.selectionSort();
        System.out.println("Sorted list using Selection Sort:");
        intList.display();

        intList.add(3);
        intList.add(1);
        intList.add(2);
        intList.mergeSort();
        System.out.println("Sorted list using Merge Sort:");
        intList.display();
    }
}

LinkedList.main(null);

Original list:
3 1 2 
Sorted list using Insertion Sort:
1 2 3 
Sorted list using Bubble Sort:
1 1 2 2 3 3 
Sorted list using Selection Sort:
1 1 1 2 2 2 3 3 3 
Sorted list using Merge Sort:
1 1 1 1 2 2 2 2 3 3 3 3 

Without Using Linked Lists

import java.util.ArrayList;
import java.util.List;

public class Collector<T extends Comparable<T>> {
    private List<T> items;

    public Collector() {
        items = new ArrayList<>();
    }

    public void add(T item) {
        items.add(item);
    }

    public List<T> getItems() {
        return items.t;
    }

    // Bubble Sort
    public void bubbleSort() {
        int n = items.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (items.get(j).compareTo(items.get(j + 1)) > 0) {
                    T temp = items.get(j);
                    items.set(j, items.get(j + 1));
                    items.set(j + 1, temp);
                }
            }
        }
    }

    // Insertion Sort
    public void insertionSort() {
        int n = items.size();
        for (int i = 1; i < n; i++) {
            T key = items.get(i);
            int j = i - 1;
            while (j >= 0 && items.get(j).compareTo(key) > 0) {
                items.set(j + 1, items.get(j));
                j = j - 1;
            }
            items.set(j + 1, key);
        }
    }

    // Merge Sort
    public void mergeSort() {
        items = mergeSort(items);
    }

    private List<T> mergeSort(List<T> list) {
        if (list.size() <= 1) {
            return list;
        }

        int middle = list.size() / 2;
        List<T> left = new ArrayList<>(list.subList(0, middle));
        List<T> right = new ArrayList<>(list.subList(middle, list.size()));

        left = mergeSort(left);
        right = mergeSort(right);

        return merge(left, right);
    }

    private List<T> merge(List<T> left, List<T> right) {
        List<T> result = new ArrayList<>();
        int leftIndex = 0, rightIndex = 0;

        while (leftIndex < left.size() && rightIndex < right.size()) {
            if (left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0) {
                result.add(left.get(leftIndex));
                leftIndex++;
            } else {
                result.add(right.get(rightIndex));
                rightIndex++;
            }
        }

        result.addAll(left.subList(leftIndex, left.size()));
        result.addAll(right.subList(rightIndex, right.size()));

        return result;
    }

    // Selection Sort
    public void selectionSort() {
        int n = items.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (items.get(j).compareTo(items.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            T temp = items.get(minIndex);
            items.set(minIndex, items.get(i));
            items.set(i, temp);
        }
    }

    public static void main(String[] args) {
        Collector<Integer> collector = new Collector<>();
        collector.add(5);
        collector.add(3);
        collector.add(8);
        collector.add(1);
        collector.add(9);

        Collector<Integer> collector2 = new Collector<>();
        collector2.add(5);
        collector2.add(3);
        collector2.add(8);
        collector2.add(1);
        collector2.add(9);

        Collector<Integer> collector3= new Collector<>();
        collector3.add(5);
        collector3.add(3);
        collector3.add(8);
        collector3.add(1);
        collector3.add(9);

        Collector<Integer> collector4= new Collector<>();
        collector4.add(5);
        collector4.add(3);
        collector4.add(8);
        collector4.add(1);
        collector4.add(9);

        System.out.println("Original: " + collector.getItems());
        System.out.println("Original: " + collector2.getItems());
        System.out.println("Original: " + collector3.getItems());
        System.out.println("Original: " + collector4.getItems());
        
        // Uncomment the sorting algorithm you want to test

        collector.bubbleSort();
        collector.insertionSort();
        collector.mergeSort();
        collector.selectionSort();

        System.out.println("Sorted: " + collector.getItems());
        System.out.println("Sorted: " + collector2.getItems());
        System.out.println("Sorted: " + collector3.getItems());
        System.out.println("Sorted: " + collector4.getItems());
    }
}