Understanding Selection Sort in Java

Sorting is a fundamental operation in computer science, and various algorithms have been developed to efficiently organize data. One such algorithm is Selection Sort, a simple yet effective sorting technique. In this article, we’ll delve into the mechanics of Selection Sort and explore how it is implemented using Java.

The Java Code:

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = { 50, 43, 38, 27, 11,40 };
        System.out.println("Before sorting:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println("\nAfter sorting:");
        selectionSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public 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;
                }
            }

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

Output:

Before sorting:
50 43 38 27 11 40
After sorting:
11 27 38 40 43 50

How Selection Sort Works:

Selection Sort is an in-place comparison sorting algorithm. It starts by dividing the input list into a sorted and an unsorted region. The algorithm then iterates through the unsorted region, finding the smallest element, and swapping it with the first unsorted element. This process continues until the entire list is sorted.

Example Usage:

Let’s consider the array {50, 43, 38, 27, 11, 40} as an example. The algorithm works as follows:

1. It finds the smallest element (11) and swaps it with the first unsorted element.
2. The array becomes {11, 43, 38, 27, 50, 40} after the first iteration.
3. The process repeats until the entire array is sorted: {11, 27, 38, 40, 43, 50}.

Complexity:

Time Complexity:

• The worst-case, average-case, and best-case time complexity of the Selection Sort are all O(n²), where n is the number of elements in the array.
• This is because, in every iteration of the outer loop, Selection Sort has to find the minimum element in the unsorted part of the array, which requires scanning through the remaining unsorted elements. This leads to quadratic time complexity.

Space Complexity:

• The space complexity of the Selection Sort is O(1), indicating that the algorithm uses a constant amount of additional memory space regardless of the size of the input.
• Selection Sort performs the sorting in place, meaning it doesn’t require additional memory proportional to the size of the input array. The only additional memory used is for a few variables (like loop counters and temporary variables), and this remains constant.

Conclusion:

Understanding how Selection Sort works and how to implement it in Java is a valuable skill for any programmer. While Selection Sort is straightforward, it may not be the most efficient for large datasets. As you explore more sorting algorithms, such as Merge Sort or Quick Sort, you’ll gain insights into their respective strengths and use cases.