Selection Sort in Java

Selection Sort is a comparison-based sorting algorithm. It works by dividing the array into two parts: a sorted part and an unsorted part. The algorithm repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted part and moves it to the end of the sorted part.

Steps of Selection Sort

Initialization:

• Start with the first element in the array.
• Assume the array has n elements.

Finding the Minimum:

• For each element in the array (from the first to the last):
  • Find the smallest element in the unsorted part of the array.
  • Swap it with the first element of the unsorted part.

Moving the Boundary:

• After placing the smallest element in its correct position, consider it as part of the sorted part.
• Move the boundary between the sorted and unsorted parts one element to the right.

Repeat Until Sorted:

• Continue the process until the entire array is sorted.

Detailed Example

Let’s sort the array [64, 34, 25, 12, 22, 11, 90] using Selection Sort.

Initial Array:

64, 34, 25, 12, 22, 11, 90

Pass 1:

• Find the smallest element in the array (11).
• Swap it with the first element (64).

Array after Pass 1:

11, 34, 25, 12, 22, 64, 90

Pass 2:

• Find the smallest element in the remaining unsorted part (12).
• Swap it with the first element of the unsorted part (34).

Array after Pass 2:

11, 12, 25, 34, 22, 64, 90

Pass 3:

• Find the smallest element in the remaining unsorted part (22).
• Swap it with the first element of the unsorted part (25).

Array after Pass 3:

11, 12, 22, 34, 25, 64, 90

Pass 4:

• Find the smallest element in the remaining unsorted part (25).
• Swap it with the first element of the unsorted part (34).

Array after Pass 4:

11, 12, 22, 25, 34, 64, 90

Pass 5:

• Find the smallest element in the remaining unsorted part (34).
• Swap it with the first element of the unsorted part (34) (no change needed).

Array after Pass 5:

11, 12, 22, 25, 34, 64, 90

Pass 6:

• Find the smallest element in the remaining unsorted part (64).
• Swap it with the first element of the unsorted part (64) (no change needed).

Array after Pass 6:

11, 12, 22, 25, 34, 64, 90

Since there is only one element left in the unsorted part, it is already in its correct position.

Final Sorted Array:

11, 12, 22, 25, 34, 64, 90

Selection Sort Java Code

public class SelectionSort {

    // Function to implement selection sort
    public static void selectionSort(int[] arr) {
        int n = arr.length; // Get the length of the array
        
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted part
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // Swap the found minimum element with the first element of the unsorted part
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    // Main method to test the selection sort function
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90}; // Sample array
        System.out.println("Original array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        selectionSort(arr); // Call selection sort function

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Code Explanation:

Function Definition:

• The selectionSort function takes an array of integers arr as input.

Outer Loop:

• for (int i = 0; i < n - 1; i++): This loop runs for n-1 passes, where n is the length of the array. Each pass finds the smallest unsorted element and moves it to the sorted part.

Finding the Minimum Element:

• int minIdx = i;: Assume the current element is the minimum.
• for (int j = i + 1; j < n; j++): This loop finds the minimum element in the unsorted part of the array.
• if (arr[j] < arr[minIdx]) { minIdx = j; }: Update the index of the minimum element if a smaller element is found.

Swapping Elements:

• int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp;: Swap the minimum element found with the first element of the unsorted part.

Main Method:

• An array arr is defined with sample values.
• The original array is printed.
• The selectionSort function is called to sort the array.
• The sorted array is printed.

OUTPUT:

Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90

Selection Sort Key Points

• Time Complexity: O(n^2) in the worst and average case.
• Space Complexity: O(1) (in-place sorting).
• Stability: Selection Sort is not stable (it does not maintain the relative order of equal elements).

Selection Sort is straightforward to understand and implement, but like Bubble Sort, it is not efficient for large datasets due to its quadratic time complexity.