Selection Sort

goes through array and finds minimum value
movies minimum to front and switches the first value with the minimum
n^2

import java.util.Arrays;
import java.util.Random;

public class SelectionSortTurtles {
    public static void main(String[] args) {
        // Create an array with 5 random values
        int[] arr = new int[5];
        Random rand = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rand.nextInt(100); // Generate a random integer between 0 and 99
        }

        // Output the original array
        System.out.println("Original turtle heights: " + Arrays.toString(arr));

        // Sort the array using selection sort
        selectionSort(arr);

        // Output the sorted array
        System.out.println("Sorted turtle heights: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++) {
            // Find the minimum element in unsorted array
            int minIndex = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

SelectionSortTurtles.main(null);

Original turtle heights: [62, 46, 29, 17, 62]
Sorted turtle heights: [17, 29, 46, 62, 62]

Insertion Sort

first for loop goes through elements finding smallest value
while loop goes backwards to find smaller value and inserts after it
n^2

import java.util.Arrays;
import java.util.Random;

public class InsertionSortTurtles {
    public static void main(String[] args) {
        // Create an array with 5 random values
        int[] arr = new int[5];
        Random rand = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rand.nextInt(100); // Generate a random integer between 0 and 99
        }

        // Output the original array
        System.out.println("Original turtle heights: " + Arrays.toString(arr));

        // Sort the array using insertion sort
        insertionSort(arr);

        // Output the sorted array
        System.out.println("Sorted turtle heights: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }
}
InsertionSortTurtles.main(null);

Original turtle heights: [72, 3, 50, 79, 80]
Sorted turtle heights: [3, 50, 72, 79, 80]

Merge Sort

divide values into two groups repeatedly until only two elements to compare
recombines in sorted method

import java.util.Arrays;
import java.util.Random;

public class MergeSortTurtles {
    public static void main(String[] args) {
        // Create an array with 5 random values
        int[] arr = new int[5];
        Random rand = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rand.nextInt(100); // Generate a random integer between 0 and 99
        }

        // Output the original array
        System.out.println("Original turtle heights: " + Arrays.toString(arr));

        // Sort the array using merge sort
        mergeSort(arr, 0, arr.length-1);

        // Output the sorted array
        System.out.println("Sorted turtle heights: " + Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

MergeSortTurtles.main(null);

Original turtle heights: [47, 29, 75, 58, 57]
Sorted turtle heights: [29, 47, 57, 58, 75]