Algo-rythmic • 29 min read

Class, to be used

This class is beachgoers, representing our people.

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

Bubble Sort

import java.util.ArrayList;
import java.util.Collections;

public class BeachgoerBubbleSort {
    public static void bubbleSort(ArrayList<Beachgoer> beachgoers) {
        int n = beachgoers.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (beachgoers.get(j).compareTo(beachgoers.get(j + 1)) > 0) {
                    // Swap beachgoers
                    Collections.swap(beachgoers, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        // Create a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = Beachgoer.createList();

        // Print original list
        System.out.println("Original List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }

        // Sort the list using Bubble Sort
        bubbleSort(beachgoerList);

        // Print sorted list
        System.out.println("\nSorted List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }
    }
}

BeachgoerBubbleSort.main(null);

Original List:
Name: Lifeguard, Length: 5
Name: Runner, Length: 6
Name: Beatboxer, Length: 3
Name: Rapper, Length: 7
Name: Beach Volleyball Dude, Length: 8
Name: Surfer, Length: 13
Name: Sandcastle, Length: 11
Name: Scuba Diver, Length: 1
Name: Click, Half Dolphin, Half Man, Length: 10
Name: M.A.T.I, Length: 9
Name: Karen, Length: 2
Name: Corn Oil, Length: 4
Name: Beach Volleyball Dudette, Length: 12

Sorted List:
Name: Scuba Diver, Length: 1
Name: Karen, Length: 2
Name: Beatboxer, Length: 3
Name: Corn Oil, Length: 4
Name: Lifeguard, Length: 5
Name: Runner, Length: 6
Name: Rapper, Length: 7
Name: Beach Volleyball Dude, Length: 8
Name: M.A.T.I, Length: 9
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Sandcastle, Length: 11
Name: Beach Volleyball Dudette, Length: 12
Name: Surfer, Length: 13

Insertion Sort

import java.util.ArrayList;

public class BeachgoerInsertionSort {
    public static void insertionSort(ArrayList<Beachgoer> beachgoers) {
        int n = beachgoers.size();
        for (int i = 1; i < n; i++) {
            Beachgoer key = beachgoers.get(i);
            int j = i - 1;
            while (j >= 0 && beachgoers.get(j).compareTo(key) > 0) {
                beachgoers.set(j + 1, beachgoers.get(j));
                j = j - 1;
            }
            beachgoers.set(j + 1, key);
        }
    }

    public static void main(String[] args) {
        // Create a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = Beachgoer.createList();

        // Print original list
        System.out.println("Original List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }

        // Sort the list using Insertion Sort
        insertionSort(beachgoerList);

        // Print sorted list
        System.out.println("\nSorted List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }
    }
}

BeachgoerInsertionSort.main(null);

Original List:
Name: Karen, Length: 2
Name: Beach Volleyball Dude, Length: 8
Name: Surfer, Length: 13
Name: Rapper, Length: 7
Name: Lifeguard, Length: 5
Name: Beach Volleyball Dudette, Length: 12
Name: Scuba Diver, Length: 1
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Runner, Length: 6
Name: Corn Oil, Length: 4
Name: M.A.T.I, Length: 9
Name: Sandcastle, Length: 11
Name: Beatboxer, Length: 3

Sorted List:
Name: Scuba Diver, Length: 1
Name: Karen, Length: 2
Name: Beatboxer, Length: 3
Name: Corn Oil, Length: 4
Name: Lifeguard, Length: 5
Name: Runner, Length: 6
Name: Rapper, Length: 7
Name: Beach Volleyball Dude, Length: 8
Name: M.A.T.I, Length: 9
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Sandcastle, Length: 11
Name: Beach Volleyball Dudette, Length: 12
Name: Surfer, Length: 13

Selection Sort

import java.util.ArrayList;

public class BeachgoerSelectionSort {
    public static void selectionSort(ArrayList<Beachgoer> beachgoers) {
        int n = beachgoers.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (beachgoers.get(j).compareTo(beachgoers.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first element of the unsorted subarray
            Beachgoer temp = beachgoers.get(minIndex);
            beachgoers.set(minIndex, beachgoers.get(i));
            beachgoers.set(i, temp);
        }
    }

    public static void main(String[] args) {
        // Create a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = Beachgoer.createList();

        // Print original list
        System.out.println("Original List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }

        // Sort the list using Selection Sort
        selectionSort(beachgoerList);

        // Print sorted list
        System.out.println("\nSorted List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }
    }
}

BeachgoerSelectionSort.main(null);

Original List:
Name: Beatboxer, Length: 3
Name: Beach Volleyball Dudette, Length: 12
Name: Lifeguard, Length: 5
Name: Rapper, Length: 7
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Surfer, Length: 13
Name: Runner, Length: 6
Name: Beach Volleyball Dude, Length: 8
Name: Sandcastle, Length: 11
Name: Scuba Diver, Length: 1
Name: Corn Oil, Length: 4
Name: M.A.T.I, Length: 9
Name: Karen, Length: 2

Sorted List:
Name: Scuba Diver, Length: 1
Name: Karen, Length: 2
Name: Beatboxer, Length: 3
Name: Corn Oil, Length: 4
Name: Lifeguard, Length: 5
Name: Runner, Length: 6
Name: Rapper, Length: 7
Name: Beach Volleyball Dude, Length: 8
Name: M.A.T.I, Length: 9
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Sandcastle, Length: 11
Name: Beach Volleyball Dudette, Length: 12
Name: Surfer, Length: 13

Merge Sort

import java.util.ArrayList;

public class BeachgoerMergeSort {
    public static void mergeSort(ArrayList<Beachgoer> beachgoers) {
        if (beachgoers.size() > 1) {
            int mid = beachgoers.size() / 2;
            
            // Split original list into two sublists
            ArrayList<Beachgoer> leftHalf = new ArrayList<>(beachgoers.subList(0, mid));
            ArrayList<Beachgoer> rightHalf = new ArrayList<>(beachgoers.subList(mid, beachgoers.size()));

            // Recursive calls to sort left and right sublists
            mergeSort(leftHalf);
            mergeSort(rightHalf);

            // Merge sorted sublists
            int i = 0, j = 0, k = 0;
            while (i < leftHalf.size() && j < rightHalf.size()) {
                if (leftHalf.get(i).compareTo(rightHalf.get(j)) <= 0) {
                    beachgoers.set(k++, leftHalf.get(i++));
                } else {
                    beachgoers.set(k++, rightHalf.get(j++));
                }
            }

            // Copy remaining elements from left sublist
            while (i < leftHalf.size()) {
                beachgoers.set(k++, leftHalf.get(i++));
            }

            // Copy remaining elements from right sublist
            while (j < rightHalf.size()) {
                beachgoers.set(k++, rightHalf.get(j++));
            }
        }
    }

    public static void main(String[] args) {
        // Create a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = Beachgoer.createList();

        // Print original list
        System.out.println("Original List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }

        // Sort the list using Merge Sort
        mergeSort(beachgoerList);

        // Print sorted list
        System.out.println("\nSorted List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }
    }
}

BeachgoerMergeSort.main(null);

Original List:
Name: Karen, Length: 2
Name: M.A.T.I, Length: 9
Name: Beach Volleyball Dudette, Length: 12
Name: Lifeguard, Length: 5
Name: Beach Volleyball Dude, Length: 8
Name: Runner, Length: 6
Name: Sandcastle, Length: 11
Name: Corn Oil, Length: 4
Name: Beatboxer, Length: 3
Name: Rapper, Length: 7
Name: Scuba Diver, Length: 1
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Surfer, Length: 13

Sorted List:
Name: Scuba Diver, Length: 1
Name: Karen, Length: 2
Name: Beatboxer, Length: 3
Name: Corn Oil, Length: 4
Name: Lifeguard, Length: 5
Name: Runner, Length: 6
Name: Rapper, Length: 7
Name: Beach Volleyball Dude, Length: 8
Name: M.A.T.I, Length: 9
Name: Click, Half Dolphin, Half Man, Length: 10
Name: Sandcastle, Length: 11
Name: Beach Volleyball Dudette, Length: 12
Name: Surfer, Length: 13

Our Sort, Broken Down

Insertion sort, but comparing fully.

import java.util.ArrayList;

public class BeachgoerInsertionSort {
    public static void insertionSort(ArrayList<Beachgoer> beachgoers) {
        int n = beachgoers.size();
        for (int i = 1; i < n; i++) {
            Beachgoer key = beachgoers.get(i);
            System.out.println("Comparing item: " + key.getName());
            int j = i - 1;
            System.out.println("Comparing key to: " + beachgoers.get(j).getName());
            while (j >= 0 && beachgoers.get(j).compareTo(key) > 0) {
                System.out.println("Comparing key to: " + beachgoers.get(j).getName());
                beachgoers.set(j + 1, beachgoers.get(j));
                j = j - 1;
            }
            beachgoers.set(j + 1, key);
        }
    }

    public static void main(String[] args) {
        // Create a list of Beachgoer objects
        ArrayList<Beachgoer> beachgoerList = Beachgoer.createShorterList();

        
        // Print original list
        System.out.println("Original List:");
        for (Beachgoer beachgoer : beachgoerList) {
            System.out.println("\t Name: " + beachgoer.getName() + ", Length: " + beachgoer.getLength());
        }

        // Sort the list using Insertion Sort
        System.out.println();
        System.out.println("=====Starting Sort=====");
        insertionSort(beachgoerList);

    }
}

BeachgoerInsertionSort.main(null);

Original List:
	 Name: Scuba Diver, Length: 1
	 Name: Beatboxer, Length: 3
	 Name: Lifeguard, Length: 5
	 Name: Karen, Length: 2
	 Name: Corn Oil, Length: 4

=====Starting Sort=====
Comparing item: Beatboxer
Comparing key to: Scuba Diver
Comparing item: Lifeguard
Comparing key to: Beatboxer
Comparing item: Karen
Comparing key to: Lifeguard
Comparing key to: Lifeguard
Comparing key to: Beatboxer
Comparing item: Corn Oil
Comparing key to: Lifeguard
Comparing key to: Lifeguard