Key Terms:

• n: Data size
• k: Number of buckets
• In-place: Uses constant memory, no extra space
• Out-place: Requires additional memory

Bubble Sort

Bubble Sort repeatedly steps through a list, comparing adjacent elements and swapping them if they are in the wrong order. The process continues until no swaps are needed, indicating the list is sorted. Smaller elements gradually "bubble" to the top.

Algoirthm Steps:

• Compare each pair of adjacent elements. Swap if the first is greater than the second.
• Repeat for every adjacent pair from start to end, placing the largest element at the end after each full pass.
• Exclude the last sorted element in subsequent passes.
• Continue until the entire list is sorted.

Implementation:

public class BubbleSorter {
    public static void sortAscending(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int swap = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = swap;
                }
            }
        }
    }

    public static <T> void sortWithComparator(T[] array, java.util.Comparator<? super T> comp) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 1; j < array.length - i; j++) {
                if (comp.compare(array[j - 1], array[j]) < 0) {
                    T temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

Complexity: Best: O(n), Worst: O(n²), Average: O(n²)

Selection Sort

Selection Sort divides the list into sorted and unsorted regions. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region.

Algorihtm Steps:

• Start with an empty sorted region and the entire list as unsorted.
• Find the minimum element in the unsorted region.
• Swap it with the first element of the unsorted region, expanding the sorted region by one.
• Repeat until the unsorted region is empty.

Implementation:

public class SelectionSorter {
    public static void sortAscending(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[minIdx]) {
                    minIdx = j;
                }
            }
            int tmp = data[i];
            data[i] = data[minIdx];
            data[minIdx] = tmp;
        }
    }

    public static <T> void sortWithComparator(T[] data, java.util.Comparator<T> comp) {
        for (int i = 0; i < data.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                if (comp.compare(data[minIndex], data[j]) < 0) {
                    minIndex = j;
                }
            }
            T swapVal = data[i];
            data[i] = data[minIndex];
            data[minIndex] = swapVal;
        }
    }
}

Complexity: Best: O(n²), Worst: O(n²), Average: O(n²)

Insertion Sort

Insertion Sort builds the sorted list one element at a time by taking each element and inserting it into its correct position within the sorted portion.

Algorithm Steps:

• Consider the first element as sorted.
• Take the next element and scan backward through the sorted elements.
• Shift sorted elements that are greater then the new element one position to the right.
• Insert the new element into the correct position.
• Repeat for all elements.

Implementation:

public class InsertionSorter {
    public static void sortAscending(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }

    public static <T> void sortWithComparator(T[] arr, java.util.Comparator<T> comp) {
        for (int i = 1; i < arr.length; i++) {
            T current = arr[i];
            int j = i - 1;
            while (j >= 0 && comp.compare(arr[j], current) < 0) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }
}

Complexity: Best: O(n), Worst: O(n²), Average: O(n²)

Shell Sort

Shell Sort is an optimization of Insertion Sort that sorts elements spaced apart by a gap, gradually reducing the gap until it becomes 1, resulting in a final insertion sort.

Algorithm Steps:

• Choose a gap sequence (e.g., dividing by 3).
• For each gap, perform a gapped insertion sort on subarrays.
• Reduce the gap and repeat until the gap is 1.

Implementation:

public class ShellSorter {
    public static void sortAscending(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 3 + 1;
            for (int i = gap; i < array.length; i++) {
                int temp = array[i];
                int j = i - gap;
                while (j >= 0 && array[j] > temp) {
                    array[j + gap] = array[j];
                    j -= gap;
                }
                array[j + gap] = temp;
            }
        }
    }

    public static <T> void sortWithComparator(T[] array, java.util.Comparator<T> comp) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 3 + 1;
            for (int i = gap; i < array.length; i++) {
                T temp = array[i];
                int j = i - gap;
                while (j >= 0 && comp.compare(array[j], temp) > 0) {
                    array[j + gap] = array[j];
                    j -= gap;
                }
                array[j + gap] = temp;
            }
        }
    }
}