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.

Practice

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

easy

A. Divide the array into halves and merge sorted halves

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

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

D. Use a pivot to partition the array into smaller parts

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

   Other options describe Merge Sort, Bubble Sort, and Quick Sort, which are different algorithms.

3. Final Answer:

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

4. Quick Check:

   Selection Sort = Find smallest and swap [OK]

Hint: Selection Sort always picks the smallest next element [OK]

Common Mistakes:

• Confusing Selection Sort with Bubble Sort
• Thinking it uses divide and conquer
• Assuming it uses a pivot element

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

easy

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

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

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

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

Solution

1. Step 1: Identify JavaScript swap syntax

   JavaScript supports swapping using destructuring assignment: [a, b] = [b, a].

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; is valid but missing let or var for temp and is verbose. arr[i], arr[minIndex] = arr[minIndex], arr[i]; is invalid syntax in JavaScript. swap(arr[i], arr[minIndex]); is a function call but no such built-in function exists.

3. Final Answer:

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

4. Quick Check:

   Destructuring swap = [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; [OK]

Hint: Use destructuring assignment for swapping in JavaScript [OK]

Common Mistakes:

• Using Python-style tuple swap syntax
• Calling undefined swap function
• Forgetting to declare temporary variable

3. What will be the output array after running Selection Sort on [29, 10, 14, 37, 13]?

medium

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

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

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

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

Solution

1. Step 1: Perform Selection Sort step-by-step

   Initial array: [29, 10, 14, 37, 13]
   Find smallest from index 0 to end: 10 at index 1, swap with 29.
   Array: [10, 29, 14, 37, 13]
   Find smallest from index 1 to end: 13 at index 4, swap with 29.
   Array: [10, 13, 14, 37, 29]
   Find smallest from index 2 to end: 14 at index 2, no swap.
   Find smallest from index 3 to end: 29 at index 4, swap with 37.
   Array: [10, 13, 14, 29, 37]

2. Step 2: Confirm final sorted array

   The array is sorted in ascending order: [10, 13, 14, 29, 37].

3. Final Answer:

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

4. Quick Check:

   Sorted array = [10, 13, 14, 29, 37] [OK]

Hint: Selection Sort places smallest element at front each pass [OK]

Common Mistakes:

• Not swapping correctly after finding minimum
• Confusing index positions during swaps
• Assuming array is unchanged

4. Identify the error in this Selection Sort code snippet:

function selectionSort(arr) {
  for (let i = 0; i < arr.length; 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];
  }
  return arr;
}

medium

A. Swapping lines overwrite values causing incorrect swaps

B. Loop ranges are incorrect, should be j < arr.length - 1

C. minIndex should be initialized outside the outer loop

D. Function does not return the sorted array

Solution

1. Step 1: Analyze the swap logic

   The swap is done by assigning arr[i] = arr[minIndex] first, then arr[minIndex] = arr[i]. This overwrites arr[i] before assigning to arr[minIndex], causing both to have the same value.

2. Step 2: Correct swap method

   Use a temporary variable or destructuring assignment to swap without overwriting:
   let temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;

3. Final Answer:

   Swapping lines overwrite values causing incorrect swaps -> Option A

4. Quick Check:

   Incorrect swap overwrites values = Swapping lines overwrite values causing incorrect swaps [OK]

Hint: Use temp variable or destructuring to swap safely [OK]

Common Mistakes:

• Swapping without temp variable
• Incorrect loop boundaries
• Not returning the array

5. Given an array with duplicate values [4, 2, 4, 3, 2], how many swaps will Selection Sort perform to fully sort it?

hard

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Trace Selection Sort swaps on the array

   Initial array: [4, 2, 4, 3, 2]
   Pass 1: smallest from index 0-4 is 2 at index 1, swap with 4 at index 0.
   Array: [2, 4, 4, 3, 2] (1 swap)
   Pass 2: smallest from index 1-4 is 2 at index 4, swap with 4 at index 1.
   Array: [2, 2, 4, 3, 4] (2 swaps)
   Pass 3: smallest from index 2-4 is 3 at index 3, swap with 4 at index 2.
   Array: [2, 2, 3, 4, 4] (3 swaps)
   Pass 4: smallest from index 3-4 is 4 at index 3, no swap.
   Pass 5: last element, no swap.

2. Step 2: Count total swaps

   Total swaps performed = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count swaps during passes = 3 [OK]

Hint: Count swaps only when minimum index differs from current index [OK]

Common Mistakes:

• Counting all comparisons as swaps
• Ignoring swaps when minIndex equals current index
• Assuming duplicates reduce swaps to zero