1. Introduction

Selection Sort is a straightforward, comparison-based sorting algorithm that divides the array into two sections:

• One part of the array is sorted.
• The remaining part is unsorted.

In every iteration, the algorithm selects the minimum element from the unsorted part and places it at the beginning of the unsorted section, effectively expanding the sorted section by one element.

2. How Selection Sort Works – Conceptual Breakdown

1. Start from the first element (index 0)
   Assume it is the smallest element (minimum).
2. Iterate through the unsorted portion of the array starting from index i + 1 to n - 1.
3. Compare each element with the current minimum
   If a smaller element is found, update the minimum index.
4. Swap the minimum element with the element at the current index i
   This moves the smallest element to its correct position in the sorted section.
5. Repeat the above steps for each position in the array
   With every pass, the sorted portion grows by one and the unsorted portion shrinks.
6. After n - 1 passes, the array is sorted because the last remaining element is already in place.

3. Pseudocode

for i from 0 to n-1
    minIndex = i
    for j from i+1 to n
        if array[j] < array[minIndex]
            minIndex = j
    swap array[i] with array[minIndex]

4. Properties of Selection Sort

Property	Description
Time Complexity	O(n²) in best, average, and worst case because it always performs n²/2 comparisons.
Space Complexity	O(1) — performs sorting in place with no additional memory.
Stable	Not stable — may change the order of equal elements during swapping.
Adaptive	Not adaptive — does not take advantage of a partially sorted array.
Swap Complexity	O(n) — performs at most (n – 1) swaps, which is fewer than bubble sort.
Comparison Type	Uses direct element comparisons. Not suitable for complex or custom orders without modification.
Use Case	Best for small arrays or when memory writes are costly (due to few swaps).

5. Java Implementation

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;

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

            // Step 1: Find the minimum in the remaining unsorted array
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Step 2: Swap the found minimum with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;

            // Step 3: Print array after each pass (optional)
            printArray(arr, i + 1);
        }
    }

    // Helper function to print current state of the array
    public static void printArray(int[] arr, int pass) {
        System.out.print("After pass " + pass + ": ");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 13};

        System.out.println("Original Array:");
        for (int num : data) {
            System.out.print(num + " ");
        }
        System.out.println("\n");

        selectionSort(data);

        System.out.println("\nSorted Array:");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

6. Visual Representation

Let’s walk through this array:
Initial array: [29, 10, 14, 37, 13]

• Pass 1
  • Compare 29 vs 10 → min = 10
  • 10 vs 14 → min = 10
  • 10 vs 37 → min = 10
  • 10 vs 13 → min = 10
  • Swap 29 and 10
    Result: [10, 29, 14, 37, 13]
• Pass 2
  • Compare 29 vs 14 → min = 14
  • 14 vs 37 → min = 14
  • 14 vs 13 → min = 13
  • Swap 29 and 13
    Result: [10, 13, 14, 37, 29]
• Pass 3
  • Compare 14 vs 37 → min = 14
  • 14 vs 29 → min = 14
  • No swap
    Result: [10, 13, 14, 37, 29]
• Pass 4
  • Compare 37 vs 29 → min = 29
  • Swap 37 and 29
    Result: [10, 13, 14, 29, 37]
• Pass 5
  • Last element is already in place.

7. When to Use Selection Sort

• When working with very small datasets (under 100 elements).
• When the number of swaps must be minimized (e.g., flash memory with write limits).
• For teaching and learning sorting concepts, especially selection and swapping.
• When you need a simple and predictable sort, and performance is not critical.
• When memory usage is a concern and you want to avoid allocating extra space.

8. Limitations

• Performs O(n²) comparisons even if the array is already sorted.
• Not efficient for large datasets; use Merge Sort, Quick Sort, or Tim Sort instead.
• Not suitable when stability matters, like sorting by name then by age.