Selection Sort in Java

Selection Sort is a simple comparison-based sorting algorithm. It repeatedly selects the smallest (or largest) element from the unsorted part of the array and places it in the correct position in the sorted part.

How Does It Work?

1. Divide the array into two parts: sorted and unsorted.
2. Find the smallest element in the unsorted part.
3. Swap the smallest element with the first element of the unsorted part.
4. Repeat the process for the rest of the array.

Steps of the Algorithm:

1. Start from the first element of the array (index i).
2. Assume the current index (i) is the position of the smallest element (minIndex).
3. Compare the elements at minIndex with the rest of the unsorted part of the array (from i + 1 to the end).
   • If a smaller element is found, update minIndex to its index.
4. Swap the smallest element (at minIndex) with the element at the current index i.
5. Move to the next index (i + 1) and repeat steps 2-4 until the array is sorted.

Understand it with an Example:

Input Array: [64, 25, 12, 22, 11]

1. Pass 1:
   • i = 0, find the smallest element in [64, 25, 12, 22, 11].
   • Smallest element: 11 at index 4.
   • Swap 64 and 11.
   • Result after Pass 1: [11, 25, 12, 22, 64].
2. Pass 2:
   • i = 1, find the smallest element in [25, 12, 22, 64].
   • Smallest element: 12 at index 2.
   • Swap 25 and 12.
   • Result after Pass 2: [11, 12, 25, 22, 64].
3. Pass 3:
   • i = 2, find the smallest element in [25, 22, 64].
   • Smallest element: 22 at index 3.
   • Swap 25 and 22.
   • Result after Pass 3: [11, 12, 22, 25, 64].
4. Pass 4:
   • i = 3, find the smallest element in [25, 64].
   • Smallest element: 25.
   • No swap is needed.
   • Result after Pass 4: [11, 12, 22, 25, 64].
5. Pass 5:
   • i = 4, only one element remains, so the array is sorted.

Output: [11, 12, 22, 25, 64]

Selection Sort Program in Java

package com.javacodepoint.sort;

public class SelectionSort {
	
	// Method to perform selection sort
	public static void selectionSort(int[] array) {
		int n = array.length;

		// Traverse through the entire array
		for (int i = 0; i < n - 1; i++) {
			// Find the minimum element in the unsorted part
			int minIndex = i;
			for (int j = i + 1; j < n; j++) {
				if (array[j] < array[minIndex]) {
					minIndex = j; // Update the index of the smallest element
				}
			}

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

	public static void main(String[] args) {
		// Example input array
		int[] numbers = { 64, 25, 12, 22, 11 };

		// Print the original array
		System.out.println("Original Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}

		// Perform selection sort
		selectionSort(numbers);

		// Print the sorted array
		System.out.println("\nSorted Array:");
		for (int num : numbers) {
			System.out.print(num + " ");
		}
	}
}

OUTPUT:

Original Array:
64 25 12 22 11
Sorted Array:
11 12 22 25 64

Explanation of the Code

1. Outer Loop (for loop at index i):
   • Iterates through the array, focusing on the current position to place the smallest element.
2. Inner Loop (for loop at index j):
   • Scans the remaining unsorted part of the array to find the smallest element.
3. Swapping:
   • The smallest element found is swapped with the element at the index i.

Time Complexity

• Best Case: O(n^2)
• Average Case: O(n^2)
• Worst Case: O(n^2)

Space Complexity

• Space: O(1) (in-place sorting).

Also Read: Insertion Sort | Bubble Sort | Merge Sort | Quick Sort