Algorythmic • 12 min read

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

class Collectable {
    // Shuffle method
    public static <T> void shuffle(ArrayList<T> list) {
        Collections.shuffle(list);
    }
}

// Person class implementing Comparable
class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // CompareTo method for sorting by age
    @Override
    public int compareTo(Person otherPerson) {
        return Integer.compare(this.age, otherPerson.age);
    }

    // CompareTo method for sorting by name
    public int compareByName(Person otherPerson) {
        return this.name.compareTo(otherPerson.name);
    }

    // ToString method
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class SuperSorting {



    public static ArrayList<Person> mergeSortReal(ArrayList<Person> list) {
        mergeSortRecursive(list, 0, list.size() - 1);
        return list;
    }

    // Merge Sort
    public static long mergeSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        mergeSortRecursive(list, 0, list.size() - 1);
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    private static void mergeSortRecursive(ArrayList<Person> list, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSortRecursive(list, left, mid);
            mergeSortRecursive(list, mid + 1, right);
            merge(list, left, mid, right);
        }
    }

    private static void merge(ArrayList<Person> list, int left, int mid, int right) {
        ArrayList<Person> temp = new ArrayList<>();
        int i = left, j = mid + 1;

        while (i <= mid && j <= right) {
            if (list.get(i).compareTo(list.get(j)) <= 0) {
                temp.add(list.get(i));
                i++;
            } else {
                temp.add(list.get(j));
                j++;
            }
        }

        while (i <= mid) {
            temp.add(list.get(i));
            i++;
        }

        while (j <= right) {
            temp.add(list.get(j));
            j++;
        }

        for (int k = left; k <= right; k++) {
            list.set(k, temp.get(k - left));
        }
    }

    // Bubble Sort
    public static long bubbleSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (list.get(j).compareTo(list.get(j + 1)) > 0) {
                    Collections.swap(list, j, j + 1);
                }
            }
        }
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    // Selection Sort
    public static long selectionSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        int n = list.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (list.get(j).compareTo(list.get(minIndex)) < 0) {
                    minIndex = j;
                }
            }
            Collections.swap(list, i, minIndex);
        }
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    // Insertion Sort
    public static long insertionSort(ArrayList<Person> list) {
        long startTime = System.nanoTime();
        int n = list.size();
        for (int i = 1; i < n; i++) {
            Person key = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j).compareTo(key) > 0) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
        long endTime = System.nanoTime();
        return endTime - startTime;
    }

    public static void main(String[] args) {
        ArrayList<Person> people = new ArrayList<>();
        // Add people with names starting from each letter of the alphabet
        for (char c = 'A'; c <= 'Z'; c++) {
            String name = String.valueOf(c);
            int age = (int) (Math.random() * 50) + 20; // Random age between 20 and 70
            people.add(new Person(name, age));
        }
        //Original list
        System.out.println("Original List: " + people);
        System.out.println("\n");

        ArrayList<Person> copy1 = new ArrayList<>(people);
        ArrayList<Person> copy2 = new ArrayList<>(people);
        ArrayList<Person> copy3 = new ArrayList<>(people);
        ArrayList<Person> copy4 = new ArrayList<>(people);


        System.out.println("Merge Sort Time: " + mergeSort(copy1) + " ns");
        System.out.println("Bubble Sort Time: " + bubbleSort(copy2) + " ns");
        System.out.println("Selection Sort Time: " + selectionSort(copy3) + " ns");
        System.out.println("Insertion Sort Time: " + insertionSort(copy4) + " ns");
        
        System.out.println("\n");
        System.out.println("Sorted Array: " + mergeSortReal(copy1));
    }
}

SuperSorting.main(null);