Sorting Algorithms in Java: Bubble, Selection, Insertion, Merge, and Quick Sort

Chapter 2: Selection Sort in Java

1. Description of Selection Sort (No Coding)

Selection Sort is a simple and efficient sorting algorithm that works by dividing the array into a sorted and unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted section.

Unlike Bubble Sort, Selection Sort minimizes the number of swaps, but it still requires O(n²) comparisons, making it inefficient for large datasets.

Working Principle of Selection Sort

1. Find the minimum element in the unsorted part of the array.
2. Swap it with the first element of the unsorted section.
3. Move the boundary between the sorted and unsorted sections one step forward.
4. Repeat until the entire array is sorted.

Visualization Example

Unsorted Array:

[5, 3, 8, 4, 2]

Pass 1 (Find minimum & swap with first element):

• Minimum = 2 → Swap with 5
• Array after swap: [2, 3, 8, 4, 5]

Pass 2 (Find minimum in remaining array & swap):

• Minimum = 3 → No swap needed
• Array remains: [2, 3, 8, 4, 5]

Pass 3 (Find minimum & swap with next element):

• Minimum = 4 → Swap with 8
• Array after swap: [2, 3, 4, 8, 5]

Pass 4 (Find minimum & swap with next element):

• Minimum = 5 → Swap with 8
• Final sorted array: [2, 3, 4, 5, 8]

2. Selection Sort Coding Examples

(a) Syllabus-Based Example (Sorting an array of numbers)

public class SelectionSortExample {

    static void selectionSort(int arr[]) {

        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {

            int minIndex = i;

            for (int j = i + 1; j < n; j++) {

                if (arr[j] < arr[minIndex]) {

                    minIndex = j;

                }

            }

            int temp = arr[minIndex];

            arr[minIndex] = arr[i];

            arr[i] = temp;

        }

    }

    public static void main(String args[]) {

        int arr[] = {5, 3, 8, 4, 2};

        selectionSort(arr);

        System.out.println(java.util.Arrays.toString(arr));

    }

}

Output:
[2, 3, 4, 5, 8]

(b) Real-World Example (Sorting employee salaries in ascending order)

public class SelectionSortSalaries {

    static void selectionSort(double salaries[]) {

        int n = salaries.length;

        for (int i = 0; i < n - 1; i++) {

            int minIndex = i;

            for (int j = i + 1; j < n; j++) {

                if (salaries[j] < salaries[minIndex]) {

                    minIndex = j;

                }

            }

            double temp = salaries[minIndex];

            salaries[minIndex] = salaries[i];

            salaries[i] = temp;

        }

    }

    public static void main(String args[]) {

        double salaries[] = {55000, 75000, 60000, 48000, 90000};

        selectionSort(salaries);

        System.out.println(java.util.Arrays.toString(salaries));

    }

}

Output:
[48000.0, 55000.0, 60000.0, 75000.0, 90000.0]

3. Advantages of Selection Sort (Pros)

✔ Simple to understand and implement – Good for beginners.
✔ Works well for small datasets – Can be used when n is small.
✔ Fewer swaps compared to Bubble Sort – This makes it better for situations where swapping is expensive.
✔ Memory-efficient – Requires O(1) extra space since it sorts in-place.
✔ Performs well when swaps are costly – Since it minimizes swaps, it is useful in cases where write operations are expensive (e.g., flash memory).

4. Disadvantages of Selection Sort (Cons)

❌ Time complexity is O(n²) – Not suitable for large datasets.
❌ Not stable – The relative order of equal elements may change.
❌ Not adaptive – It does not detect if the array is already sorted and always performs O(n²) comparisons.
❌ Less efficient than Insertion Sort for nearly sorted data – Insertion Sort runs in O(n) for nearly sorted arrays, while Selection Sort still takes O(n²).
❌ Limited real-world usage – More efficient algorithms like Quick Sort and Merge Sort are preferred.

5. How is Selection Sort Better Than Other Sorting Techniques?

• Better than Bubble Sort in terms of swaps – Uses fewer swaps, making it more efficient when swaps are expensive.
• Does not require additional memory – Unlike Merge Sort, which requires O(n) space, Selection Sort sorts in O(1) space.
• Works well for scenarios with expensive write operations – Example: Sorting large datasets stored in flash memory where writes are costly.
• Easier to implement than Quick Sort or Merge Sort – Requires no complex recursion or partitioning.
• Performs consistently regardless of input order – Unlike Quick Sort, which has a worst-case O(n²), Selection Sort consistently runs in O(n²).

6. Best Cases to Use Selection Sort

✔ When the dataset is small (n < 10-20) – Simple implementation is an advantage.
✔ When minimizing swaps is important – Example: Sorting elements in flash memory.
✔ When sorting is done in place with limited memory – Since it does not use extra space.
✔ When data is stored on external storage – Selection Sort minimizes swaps, reducing disk writes.
✔ When a predictable performance is needed – It always runs in O(n²), unlike Quick Sort, which may degrade to O(n²).

7. Worst Cases to Use Selection Sort

❌ When dealing with large datasets – Other algorithms like Merge Sort (O(n log n)) are much faster.
❌ When stability is required – It does not maintain the relative order of equal elements.
❌ When the array is already sorted – Unlike Bubble Sort or Insertion Sort, it still performs O(n²) comparisons.
❌ When adaptive behavior is required – Cannot optimize for nearly sorted arrays.
❌ When a highly efficient algorithm is needed – Merge Sort or Quick Sort are far superior.

Final Thoughts

Selection Sort is a simple but inefficient sorting algorithm. It is best suited for small datasets or cases where minimizing swaps is crucial. However, for larger datasets, Quick Sort, Merge Sort, or Heap Sort are significantly better choices. 🚀