Bubble Sort Algorithm

Bubble Sort is a straightforward comparison-based sorting technique that repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. The process continues until the list is sorted.

Implementation Steps:

1. Iterate through the array comparing adjacent elements
2. Swap elements if they're in incorrect order
3. Repeat the process for each element, reducing the range by one each iteration
4. Continue until no more swaps are needed

Java Implementation:

class ArraySorter {
    void bubbleSort(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    int swap = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = swap;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] values = {29, 10, 14, 37, 13};
        new ArraySorter().bubbleSort(values);
        System.out.println("Sorted array: ");
        for (int value : values) {
            System.out.print(value + " ");
        }
    }
}

Performance Characteristics:

• Time Complexity: O(n²) in average and worst cases, O(n) in best case
• Space Complexity: O(1)
• Stability: Maintains relative order of equal elements
• Use Case: Suitable for small datasets or educational purposes

Selection Sort Algorithm

Selection Sort works by dividing the input list in to two parts: the sorted portion and the unsorted portion. The algorithm repeatedly selects the smallest element from the unsorted portion and moves it to the end of the sorted portion.

Implementation Steps:

1. Identify the smallest element in the unsorted section
2. Swap it with the first element of the unsorted section
3. Expand the sorted section by one element
4. Repeat until the entire array is sorted

Java Implementation:

class ArraySelector {
    void selectionSort(int[] elements) {
        for (int current = 0; current < elements.length - 1; current++) {
            int minPosition = current;
            for (int next = current + 1; next < elements.length; next++) {
                if (elements[next] < elements[minPosition]) {
                    minPosition = next;
                }
            }
            int temporary = elements[current];
            elements[current] = elements[minPosition];
            elements[minPosition] = temporary;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {21, 7, 32, 15, 4};
        new ArraySelector().selectionSort(numbers);
        System.out.println("Sorted elements: ");
        for (int number : numbers) {
            System.out.print(number + " ");
        }
    }
}

Performance Characteristics:

• Time Complexity: O(n²) in all cases
• Space Complexity: O(1)
• Stability: Does not maintain order of equal elements
• Use Case: Primarily for educational purposes or very small datasets

Java's Built-in Sorting Methods

Java provides efficient sorting implementations through Arrays.sort() and Collections.sort() methods.

Arrays.sort() Example:

import java.util.Arrays;

class BuiltInSorter {
    public static void main(String[] args) {
        int[] values = {45, 12, 78, 23, 56};
        Arrays.sort(values);
        System.out.println(Arrays.toString(values));
    }
}

Collections.sort() Example:

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

class ItemSorter {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>();
        items.add("Book");
        items.add("Pen");
        items.add("Notebook");
        Collections.sort(items);
        System.out.println(items);
    }
}

Built-in Sort Features:

• Optimized Algorithms: Uses efficient implementations like Timsort
• Flexibility: Supports custom comparators
• Stability: Maintains order of equal elements
• Performance: Typically O(n log n) time complexity