Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Basic Selection Sort

Problem Statement

Write a Java program that implements the Selection Sort algorithm to sort an array of integers in ascending order. The program should count the number of swaps performed during sorting and test the implementation with various input arrays, including unsorted, already sorted, reversed, and arrays with duplicate elements. Selection Sort repeatedly finds the minimum element from the unsorted portion of the array and swaps it with the first unsorted element, building the sorted portion from the start. You can visualize this as selecting the smallest item from a pile and placing it at the front, repeating until the pile is sorted.

Input:

  • An array of integers to be sorted. Output: The sorted array, the number of swaps performed, and a string representation of the input and sorted arrays for clarity. Constraints:
  • The array length n is between 0 and 10^5.
  • Array elements are integers in the range [-10^9, 10^9]. Example:
  • Input: array = [64, 34, 25, 12, 22]
  • Output:
    • Input Array: [64, 34, 25, 12, 22]
    • Sorted Array: [12, 22, 25, 34, 64]
    • Swaps: 4
  • Explanation: Selection Sort finds the minimum in each pass, swapping it to the front, resulting in 4 swaps.
  • Input: array = [1, 2, 3]
  • Output:
    • Input Array: [1, 2, 3]
    • Sorted Array: [1, 2, 3]
    • Swaps: 0
  • Explanation: Already sorted array requires no swaps.

Pseudocode

FUNCTION selectionSort(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        SET minIdx to i
        FOR j from i+1 to n-1
            IF arr[j] < arr[minIdx] THEN
                SET minIdx to j
            ENDIF
        ENDFOR
        IF minIdx != i THEN
            SET temp to arr[i]
            SET arr[i] to arr[minIdx]
            SET arr[minIdx] to temp
            INCREMENT swaps
        ENDIF
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of input arrays
    FOR each testCase in testCases
        PRINT test case details
        CREATE copy of testCase array
        SET swaps to selectionSort(copy)
        PRINT input array, sorted array, and swaps
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define selectionSort: a. Initialize a counter swaps to 0. b. For each index i from 0 to n-1:
    • Find the minimum element’s index minIdx in arr[i..n-1].
    • If minIdx != i, swap arr[i] with arr[minIdx] and increment swaps. c. Return the number of swaps.
  2. Define toString: a. Convert the array to a string, e.g., "[64, 34, 25, 12, 22]".
  3. In main, test with: a. An unsorted array. b. An already sorted array. c. A reversed array. d. An array with duplicates. e. An empty array.

Java Implementation

import java.util.*;

public class BasicSelectionSort {
    // Performs Selection Sort and counts swaps
    public int selectionSort(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                // Swap elements
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
                swaps++;
            }
        }
        return swaps;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            result.append(arr[i]);
            if (i < arr.length - 1) {
                result.append(", ");
            }
        }
        result.append("]");
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;

        TestCase(int[] arr) {
            this.arr = arr;
        }
    }

    // Main method to test Selection Sort
    public static void main(String[] args) {
        BasicSelectionSort sorter = new BasicSelectionSort();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{64, 34, 25, 12, 22}), // Unsorted
            new TestCase(new int[]{1, 2, 3, 4, 5}),      // Sorted
            new TestCase(new int[]{5, 4, 3, 2, 1}),      // Reversed
            new TestCase(new int[]{3, 1, 3, 2, 1}),      // Duplicates
            new TestCase(new int[]{})                     // Empty
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            int[] arr = testCases[i].arr.clone(); // Copy to preserve original
            System.out.println("Input Array: " + sorter.toString(arr));
            int swaps = sorter.selectionSort(arr);
            System.out.println("Sorted Array: " + sorter.toString(arr));
            System.out.println("Swaps: " + swaps + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input Array: [64, 34, 25, 12, 22]
Sorted Array: [12, 22, 25, 34, 64]
Swaps: 4

Test case 2:
Input Array: [1, 2, 3, 4, 5]
Sorted Array: [1, 2, 3, 4, 5]
Swaps: 0

Test case 3:
Input Array: [5, 4, 3, 2, 1]
Sorted Array: [1, 2, 3, 4, 5]
Swaps: 4

Test case 4:
Input Array: [3, 1, 3, 2, 1]
Sorted Array: [1, 1, 2, 3, 3]
Swaps: 3

Test case 5:
Input Array: []
Sorted Array: []
Swaps: 0

Explanation:

  • Test case 1: Unsorted array requires 4 swaps to sort.
  • Test case 2: Already sorted array requires 0 swaps.
  • Test case 3: Reversed array requires 4 swaps.
  • Test case 4: Array with duplicates requires 3 swaps.
  • Test case 5: Empty array requires 0 swaps.

How It Works

  • selectionSort:
    • Iterates through the array, finding the minimum element in the unsorted portion.
    • Swaps the minimum with the first unsorted element if needed, incrementing swaps.
    • Builds the sorted portion from the start.
  • toString: Formats array as a string for output.
  • Example Trace (Test case 1):
    • Pass 1: Find min=12 at index 3, swap with 64: [12, 34, 25, 64, 22] (1 swap).
    • Pass 2: Find min=22 at index 4, swap with 34: [12, 22, 25, 64, 34] (1 swap).
    • Pass 3: Find min=25 at index 2, no swap: [12, 22, 25, 64, 34].
    • Pass 4: Find min=34 at index 4, swap with 64: [12, 22, 25, 34, 64] (1 swap).
    • Pass 5: Find min=64, no swap. Total swaps: 4.
  • Main Method: Tests unsorted, sorted, reversed, duplicates, and empty arrays.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
selectionSortO(n²)O(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for selectionSort (n passes, up to n comparisons each); O(n) for toString (iterate array).
  • Space complexity: O(1) for selectionSort (in-place); O(n) for toString (string builder).
  • Selection Sort always performs O(n²) comparisons, but swaps are O(n) in the worst case.

✅ Tip: Selection Sort is simple and in-place, ideal for small arrays or when minimizing swaps is important. Use it when write operations are costly compared to comparisons.

⚠ Warning: Ensure the array is copied before sorting to preserve the original for display. Handle empty arrays to avoid index issues in the sorting loop.