Selection Sort Algorithm in DSA Java - Time & Space Complexity

Time Complexity: Selection Sort Algorithm

O(n²)

Understanding Time Complexity

We want to understand how the time needed to sort a list grows as the list gets bigger using selection sort.

How does the number of steps change when the list size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}
    

This code sorts an array by repeatedly finding the smallest remaining element and swapping it to the front.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing elements inside the inner loop to find the minimum.
• How many times: The outer loop runs n-1 times, and for each outer loop, the inner loop runs fewer times, roughly n-i-1 times.

How Execution Grows With Input

As the list grows, the number of comparisons grows much faster because each new element is compared with many others.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: The number of operations grows roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if the list doubles in size, the time to sort roughly quadruples.

Common Mistake

[X] Wrong: "Selection sort gets faster if the list is already sorted."

[OK] Correct: Selection sort always compares all pairs the same way, so it takes the same time regardless of order.

Interview Connect

Knowing selection sort's time complexity helps you understand why more efficient sorting methods are preferred for large data, a useful insight in coding interviews.

Self-Check

"What if we changed the inner loop to stop early when no smaller element is found? How would the time complexity change?"

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