Selection Sort Algorithm in DSA Java

Mental Model

Selection sort finds the smallest item and puts it at the start, then repeats for the rest.

Analogy: Imagine picking the smallest apple from a basket and placing it in a new row, then picking the next smallest from the remaining apples, and so on.

Unsorted array:
[7, 3, 5, 2, 4]
Indexes:
 0  1  2  3  4

Dry Run Walkthrough

Input: array: [7, 3, 5, 2, 4]

Goal: Sort the array in ascending order using selection sort

Step 1: Find smallest from index 0 to end (2 at index 3), swap with index 0

[2, 3, 5, 7, 4]

Why: Put the smallest element at the start

Step 2: Find smallest from index 1 to end (3 at index 1), swap with index 1

[2, 3, 5, 7, 4]

Why: Next smallest is already in place

Step 3: Find smallest from index 2 to end (4 at index 4), swap with index 2

[2, 3, 4, 7, 5]

Why: Place next smallest at correct position

Step 4: Find smallest from index 3 to end (5 at index 4), swap with index 3

[2, 3, 4, 5, 7]

Why: Place next smallest at correct position

Step 5: Only one element left at index 4, no swap needed

[2, 3, 4, 5, 7]

Why: Last element is already sorted

Result:

Sorted array:
[2, 3, 4, 5, 7]

Annotated Code

DSA Java

public class SelectionSort {
    // Function to perform selection sort on array
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // assume current i is smallest
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // found smaller element
                }
            }
            // swap smallest found with element at i
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    // Helper to print array
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {7, 3, 5, 2, 4};
        System.out.println("Original array:");
        printArray(arr);
        selectionSort(arr);
        System.out.println("Sorted array:");
        printArray(arr);
    }
}

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

iterate over each position to place the smallest element

int minIndex = i; // assume current i is smallest

start by assuming current position holds smallest value

for (int j = i + 1; j < n; j++) {

search the rest of the array for a smaller element

if (arr[j] < arr[minIndex]) { minIndex = j; }

update minIndex when a smaller element is found

swap arr[minIndex] and arr[i]

place the smallest found element at the current position

Output

Original array:

7 3 5 2 4 

Sorted array:

2 3 4 5 7 

Complexity Analysis

Time: O(n^2) because for each element we scan the rest to find the smallest

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to bubble sort, selection sort does fewer swaps but same comparisons; simpler but still quadratic time

Edge Cases

empty array

no operations, array remains empty

DSA Java

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

array with one element

no swaps needed, array stays same

DSA Java

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

array with all elements equal

no swaps needed, array stays same

DSA Java

if (arr[j] < arr[minIndex]) { minIndex = j; }

When to Use This Pattern

When you need a simple sorting method that repeatedly picks the smallest item and places it in order, selection sort is a good first approach.

Common Mistakes

Mistake: Swapping elements inside the inner loop instead of after finding the minimum
Fix: Only swap once per outer loop iteration after finding the minimum index

Summary

Selection sort repeatedly finds the smallest element and moves it to the front.

Use it when you want a simple, easy-to-understand sorting method for small arrays.

The key insight is to select the minimum element in the unsorted part and swap it once per pass.

Practice

1. What is the main idea behind the Selection Sort algorithm?

easy

A. Repeatedly find the smallest element and move it to the front

B. Divide the list into halves and sort each half recursively

C. Swap adjacent elements if they are in wrong order repeatedly

D. Use a heap data structure to sort elements efficiently

Solution

1. Step 1: Understand Selection Sort process

   Selection Sort works by finding the smallest element in the unsorted part and swapping it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Unlike divide and conquer or adjacent swaps, Selection Sort directly selects the minimum each time.

3. Final Answer:

   Repeatedly find the smallest element and move it to the front -> Option A

4. Quick Check:

   Selection Sort = Find min and swap [OK]

Hint: Selection Sort picks smallest element each pass [OK]

Common Mistakes:

• Confusing Selection Sort with Bubble Sort
• Thinking it divides the list recursively
• Assuming it uses extra data structures

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[minIndex] in Java during Selection Sort?

easy

A. arr[i] = arr[minIndex]; arr[minIndex] = arr[i];

B. swap(arr[i], arr[minIndex]);

C. temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;

D. arr[i], arr[minIndex] = arr[minIndex], arr[i];

Solution

1. Step 1: Understand Java swap syntax

   Java does not have a built-in swap function; we use a temporary variable to swap values.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; correctly uses a temporary variable. arr[i] = arr[minIndex]; arr[minIndex] = arr[i]; overwrites arr[i] before saving it. swap(arr[i], arr[minIndex]); is invalid syntax. arr[i], arr[minIndex] = arr[minIndex], arr[i]; is Python style, not Java.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; -> Option C

4. Quick Check:

   Use temp variable to swap in Java [OK]

Hint: Use temp variable to swap in Java [OK]

Common Mistakes:

• Trying to swap without temp variable
• Using Python or other language syntax
• Overwriting one element before saving it

3. What will be the output array after running Selection Sort on int[] arr = {29, 10, 14, 37, 13};?

medium

A. [10, 14, 13, 29, 37]

B. [29, 10, 14, 37, 13]

C. [13, 10, 14, 29, 37]

D. [10, 13, 14, 29, 37]

Solution

1. Step 1: Perform first pass to find minimum

   Minimum is 10, swap with 29: [10, 29, 14, 37, 13]

2. Step 2: Perform second pass to find next minimum

   Minimum in remaining is 13, swap with 29: [10, 13, 14, 37, 29]

3. Step 3: Continue sorting

   Next minimum is 14 (already in place), then 29 and 37 sorted: [10, 13, 14, 29, 37]

4. Final Answer:

   [10, 13, 14, 29, 37] -> Option D

5. Quick Check:

   Selection Sort output = sorted array [OK]

Hint: Selection Sort outputs sorted array ascending [OK]

Common Mistakes:

• Not swapping correctly after finding minimum
• Confusing indices during swaps
• Stopping sorting early

4. Consider this buggy Selection Sort snippet:

for (int i = 0; i < arr.length; i++) {
  int minIndex = i;
  for (int j = i + 1; j < arr.length; j++) {
    if (arr[j] > arr[minIndex]) {
      minIndex = j;
    }
  }
  int temp = arr[i];
  arr[i] = arr[minIndex];
  arr[minIndex] = temp;
}

What is the error?

medium

A. The inner loop condition should be j <= arr.length

B. The comparison should be arr[j] < arr[minIndex] to find minimum

C. The swap is done before finding minimum

D. The outer loop should start from 1 instead of 0

Solution

1. Step 1: Analyze the comparison in inner loop

   The code uses arr[j] > arr[minIndex], which finds the maximum, not minimum.

2. Step 2: Correct the comparison for Selection Sort

   Selection Sort requires finding the minimum, so comparison should be arr[j] < arr[minIndex].

3. Final Answer:

   The comparison should be arr[j] < arr[minIndex] to find minimum -> Option B

4. Quick Check:

   Selection Sort finds minimum, so use < comparison [OK]

Hint: Use less than to find minimum in Selection Sort [OK]

Common Mistakes:

• Using greater than instead of less than
• Changing loop bounds incorrectly
• Swapping before finding minimum

5. You want to sort an array but only partially: after Selection Sort runs for 2 passes on int[] arr = {20, 5, 15, 10, 25}, what is the array state?

hard

A. [5, 10, 15, 25, 20]

B. [5, 10, 15, 20, 25]

C. [5, 15, 10, 20, 25]

D. [5, 15, 10, 25, 20]

Solution

1. Step 1: First pass finds minimum

   Minimum is 5, swap with 20: [5, 20, 15, 10, 25]

2. Step 2: Second pass finds next minimum in remaining

   Minimum in [20, 15, 10, 25] is 10, swap with 20: [5, 10, 15, 20, 25]

3. Step 3: Array after 2 passes

   Array is [5, 10, 15, 20, 25]

4. Final Answer:

   [5, 10, 15, 25, 20] -> Option A

5. Quick Check:

   Two passes partially sort array [OK]

Hint: Each pass places one smallest element correctly [OK]

Common Mistakes:

• Not swapping correctly after each pass
• Confusing which elements are sorted
• Assuming full sort after 2 passes