Bubble, Selection, and Insertion Sort

These are the three basic, intuitive sorting algorithms. Their time complexity is generally O(n^2), making them inefficient for large datasets, but they are crucial for understanding algorithm mechanics and in-place sorting.

1. Bubble Sort

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. This "bubbles" the largest elements to the top (end) of the array.

public class BubbleSort {
    public void sort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // Last i elements are already in place
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

• Time Complexity: Worst O(n^2), Best O(n) (if already sorted and optimized with a flag).
• Space Complexity: O(1)

2. Selection Sort

Selection Sort sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.

public class SelectionSort {
    public void sort(int arr[]) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }

            // Swap the found minimum element with the first element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

• Time Complexity: O(n^2) in all cases.
• Space Complexity: O(1)

3. Insertion Sort

Insertion Sort works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

public class InsertionSort {
    public void sort(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 = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

• Time Complexity: Worst O(n^2), Best O(n).
• Space Complexity: O(1)