Selection Sort Algorithm in DSA Javascript - 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

↓

i < array length - 1?

No→Sorted array ready

↩Back to find min element

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

Execution Sample

DSA Javascript

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

Sorts the array by selecting the smallest element in each pass and swapping it to the front.

Execution Table

Step	Operation	Current i	Current j	Min Index	Array State	Swap Occurred
1	Initialize i=0	0	-	0	[5, 3, 8, 1, 2]	No
2	Compare arr[j]=3 < arr[minIndex]=5	0	1	1	[5, 3, 8, 1, 2]	No
3	Compare arr[j]=8 < arr[minIndex]=3	0	2	1	[5, 3, 8, 1, 2]	No
4	Compare arr[j]=1 < arr[minIndex]=3	0	3	3	[5, 3, 8, 1, 2]	No
5	Compare arr[j]=2 < 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	Increment i=1	1	-	1	[1, 3, 8, 5, 2]	No
8	Compare arr[j]=8 < arr[minIndex]=3	1	2	1	[1, 3, 8, 5, 2]	No
9	Compare arr[j]=5 < arr[minIndex]=3	1	3	1	[1, 3, 8, 5, 2]	No
10	Compare arr[j]=2 < 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	Increment i=2	2	-	2	[1, 2, 8, 5, 3]	No
13	Compare arr[j]=5 < arr[minIndex]=8	2	3	3	[1, 2, 8, 5, 3]	No
14	Compare arr[j]=3 < 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	Increment i=3	3	-	3	[1, 2, 3, 5, 8]	No
17	Compare arr[j]=8 < 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	Increment i=4	4	-	4	[1, 2, 3, 5, 8]	No
20	i=4 equals arr.length-1=4, sorting done	4	-	-	[1, 2, 3, 5, 8]	No

💡 i reaches 4 which is arr.length - 1, so sorting is 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	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?

In step 18, swapping arr[i] with itself does nothing but keeps the algorithm consistent; no change occurs as shown in the execution_table row 18.

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

Because elements before i are already sorted, so we only look for the minimum in the unsorted part, as shown in execution_table steps 2-5 for i=0.

When does the sorting stop?

Sorting stops when i reaches arr.length - 1, because the last element is then in place, as shown in execution_table step 20.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the array state after the swap?

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

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

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

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

💡 Hint

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

At which step does the minIndex first change from 0 to another value?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Min Index' column changes in the first few steps in execution_table.

If the array was already sorted, how many swaps would occur?

A None

B One per iteration

C Swaps only when minIndex != i

D Swaps every step

💡 Hint

Refer to the 'Swap Occurred' column and note when swaps happen in execution_table.

Concept Snapshot

Selection Sort Algorithm:
- Loop i from 0 to length-2
- Find min element index from i to end
- Swap min element with element at i
- Repeat until array sorted
- Time: O(n²), Space: O(1)
- In-place, unstable sort

Full Transcript

Selection sort works by dividing the array into a sorted and unsorted part. It repeatedly finds the smallest element in the unsorted part and swaps it with the first unsorted element, moving the boundary forward. The process continues until the entire array is sorted. The algorithm uses two loops: the outer loop moves the boundary, and the inner loop finds the minimum element. Swapping occurs even if the minimum element is at the current position, but this has no effect. Sorting stops when the outer loop reaches the last element. The time complexity is quadratic, and it sorts the array in place without extra space.