Selection Sort Algorithm in DSA Java - Execution Trace

Concept Flow - Selection Sort Algorithm

Start with unsorted array

↓

Set i = 0 (start index)

↓

Find min element from i to end

↓

Swap min element with element at i

↓

Increment i

↓

Is i < array length - 1?

No→Sorted array, Done

↩Back to find min element

Selection sort repeatedly finds the smallest element in the unsorted part and swaps it to the front, moving the boundary of sorted and unsorted parts forward.

Execution Sample

DSA Java

int[] arr = {5, 3, 8, 1, 2};
for (int i = 0; i < arr.length - 1; i++) {
  int minIndex = i;
  for (int j = i + 1; j < arr.length; j++) {
    if (arr[j] < arr[minIndex]) minIndex = j;
  }
  int temp = arr[minIndex];
  arr[minIndex] = arr[i];
  arr[i] = temp;
}

Sorts the array by selecting the smallest element from the unsorted part and swapping it with the first unsorted element.

Execution Table

Step	Operation	Current i	Current j	minIndex	Array State	Swap Occurred
1	Initialize i=0, minIndex=0	0	-	0	[5, 3, 8, 1, 2]	No
2	Compare arr[j]=3 with arr[minIndex]=5	0	1	1	[5, 3, 8, 1, 2]	No
3	Compare arr[j]=8 with arr[minIndex]=3	0	2	1	[5, 3, 8, 1, 2]	No
4	Compare arr[j]=1 with arr[minIndex]=3	0	3	3	[5, 3, 8, 1, 2]	No
5	Compare arr[j]=2 with arr[minIndex]=1	0	4	3	[5, 3, 8, 1, 2]	No
6	Swap arr[i]=5 with arr[minIndex]=1	0	-	3	[1, 3, 8, 5, 2]	Yes
7	Initialize i=1, minIndex=1	1	-	1	[1, 3, 8, 5, 2]	No
8	Compare arr[j]=8 with arr[minIndex]=3	1	2	1	[1, 3, 8, 5, 2]	No
9	Compare arr[j]=5 with arr[minIndex]=3	1	3	1	[1, 3, 8, 5, 2]	No
10	Compare arr[j]=2 with arr[minIndex]=3	1	4	4	[1, 3, 8, 5, 2]	No
11	Swap arr[i]=3 with arr[minIndex]=2	1	-	4	[1, 2, 8, 5, 3]	Yes
12	Initialize i=2, minIndex=2	2	-	2	[1, 2, 8, 5, 3]	No
13	Compare arr[j]=5 with arr[minIndex]=8	2	3	3	[1, 2, 8, 5, 3]	No
14	Compare arr[j]=3 with arr[minIndex]=5	2	4	4	[1, 2, 8, 5, 3]	No
15	Swap arr[i]=8 with arr[minIndex]=3	2	-	4	[1, 2, 3, 5, 8]	Yes
16	Initialize i=3, minIndex=3	3	-	3	[1, 2, 3, 5, 8]	No
17	Compare arr[j]=8 with arr[minIndex]=5	3	4	3	[1, 2, 3, 5, 8]	No
18	Swap arr[i]=5 with arr[minIndex]=5	3	-	3	[1, 2, 3, 5, 8]	No
19	i=4, loop ends	4	-	-	[1, 2, 3, 5, 8]	No

💡 i reaches 4, condition i < arr.length - 1 (4 < 4) is False, sorting complete

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 18	Final
i	0	1	2	3	4	4
minIndex	0	3	4	4	3	-
Array	[5, 3, 8, 1, 2]	[1, 3, 8, 5, 2]	[1, 2, 8, 5, 3]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we swap even if minIndex is the same as i (like in step 18)?

Swapping the element with itself does not change the array but keeps the algorithm consistent. Step 18 shows no change in array and no swap flag, confirming this.

Why does the inner loop start from j = i + 1 instead of 0?

Because elements before i are already sorted, so we only look for the minimum in the unsorted part. Execution_table rows 2-5 show comparisons starting from j=1 when i=0.

When does the sorting stop?

Sorting stops when i reaches the last index minus one, as shown in step 19 where i=4 and the loop condition fails, meaning the array is fully sorted.

Visual Quiz - 3 Questions

Look at the execution table at step 6. What is the array state after the swap?

A [5, 3, 8, 1, 2]

B [1, 2, 8, 5, 3]

C [1, 3, 8, 5, 2]

D [3, 1, 8, 5, 2]

💡 Hint

Check the 'Array State' column at step 6 in the execution_table.

At which step does minIndex first change from its initial value during i=0?

A Step 3

B Step 2

C Step 4

D Step 5

💡 Hint

Look at the 'minIndex' column for i=0 in the execution_table rows 2-5.

If the array was already sorted, how would the 'Swap Occurred' column change?

A Swaps would never occur

B All swaps would be 'Yes'

C Swaps would occur only at the last step

D Swaps would occur randomly

💡 Hint

Refer to the 'Swap Occurred' column and consider what happens if minIndex always equals i.

Concept Snapshot

Selection Sort Algorithm:
- Repeatedly find the smallest element in unsorted part
- Swap it with the first unsorted element
- Move boundary of sorted part forward
- Time complexity: O(n²)
- In-place and unstable sort

Full Transcript

Selection sort works by dividing the array into sorted and unsorted parts. Starting from the first element, it finds the smallest element in the unsorted part and swaps it with the current position. This process repeats by moving the starting index forward until the entire array is sorted. The execution table shows each comparison and swap step, tracking the current index i, the scanning index j, the minimum element index minIndex, and the array state after each operation. Key moments clarify why swaps happen even when minIndex equals i, why the inner loop starts from i+1, and when the sorting stops. The visual quiz tests understanding of array states and variable changes during execution.

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