Selection Sort Algorithm in DSA Javascript

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.

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

Start with first element (↑ at index 0)

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; swap with index 0

[2, 3, 5, 7, 4]
Indexes:  0  1  2  3  4
↑ at index 0

Why: We put the smallest number (2) at the start to begin sorting

Step 2: Find smallest from index 1 to end; swap with index 1

[2, 3, 5, 7, 4]
Indexes:  0  1  2  3  4
↑ at index 1

Why: Next smallest (3) is already at index 1, so no swap needed

Step 3: Find smallest from index 2 to end; swap with index 2

[2, 3, 4, 7, 5]
Indexes:  0  1  2  3  4
↑ at index 2

Why: Smallest from remaining is 4, swap it with 5 at index 2

Step 4: Find smallest from index 3 to end; swap with index 3

[2, 3, 4, 5, 7]
Indexes:  0  1  2  3  4
↑ at index 3

Why: Smallest from last two is 5, swap with 7 at index 3

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

[2, 3, 4, 5, 7]
Indexes:  0  1  2  3  4
Sorting complete

Why: Last element is in place, array is sorted

Result:

[2, 3, 4, 5, 7]

Annotated Code

DSA Javascript

class SelectionSort {
  static sort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
      let minIndex = i;
      // find index of smallest element in unsorted part
      for (let j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }
      // swap smallest found with element at i
      if (minIndex !== i) {
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
      }
    }
    return arr;
  }
}

// Driver code
const inputArray = [7, 3, 5, 2, 4];
const sortedArray = SelectionSort.sort(inputArray);
console.log(sortedArray.join(", ") + "\n");

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

iterate over each position to place the smallest element

let minIndex = i;

assume current position holds smallest element

for (let 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

if (minIndex !== i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; }

swap the smallest element found with current position

Output

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 still has O(n^2) comparisons

Edge Cases

empty array

returns empty array immediately without error

DSA Javascript

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

array with one element

returns the same single-element array unchanged

DSA Javascript

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

array with all elements equal

no swaps occur, array remains unchanged

DSA Javascript

if (minIndex !== i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; }

When to Use This Pattern

When you need a simple, easy-to-understand sorting method and can afford O(n^2) time, selection sort is a good first choice.

Common Mistakes

Mistake: Swapping elements inside the inner loop instead of after finding the minimum
Fix: Only swap once after the inner loop finishes to place the smallest element

Mistake: Not updating minIndex when a smaller element is found
Fix: Update minIndex inside the inner loop whenever a smaller element is found

Summary

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

Use it when you want a simple sorting method and the list is small or nearly sorted.

The key insight is to find the smallest element in the unsorted part and swap it once per iteration.

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