4. Selection Sort Algorithm

This page discusses Selection Sort algorithm using recursion and iteration.

We've seen Problems on arrays, where we process one single element in every recursive call (key takeaways).
Using this approach, we can recursively sort an array, leading to the Selection Sort algorithm.

• At each step, find the smallest element from the remaining unsorted portion.
• Swap it with the current element.
• Recursively/Iteratively repeat for the remaining unsorted portion.

---

1. Recursive Approach

Using recursion, we sort an array element by element.

let arr = [5, 3, 8, 1, 2];

// Expected sorted array: [1, 2, 3, 5, 8]

Recursive Code

function selectionSort(arr, index = 0) {
  // Base case: If all elements are sorted
  if (index === arr.length) {
    return;
  }

  // Find the minimum element in the remaining unsorted array
  let minIndex = index;
  for (let i = index + 1; i < arr.length; i++) {
    if (arr[i] < arr[minIndex]) {
      minIndex = i;
    }
  }

  // Swap elements
  [arr[index], arr[minIndex]] = [arr[minIndex], arr[index]];

  // Recursive call for the next index
  selectionSort(arr, index + 1);
}

// Example usage
let arr = [5, 3, 8, 1, 2];
selectionSort(arr);
console.log(arr); // Output: [1, 2, 3, 5, 8]

Time Complexity - O(n²)

• The recursive function runs n times, (O(n) work)
• In each call, we find the minimum element (O(n) work).
• Total complexity = O(n) * O(n) = O(n²).

Space Complexity - O(n)

• Recursion depth = n (each function call is stored in the call stack) -> O(n) auxiliary space.
• No extra data structures used.

---

2. Iterative Approach (Using Loops)

Using iteration (outer for loop), we sort an array element by element.

let arr = [5, 3, 8, 1, 2];

// Expected sorted array: [1, 2, 3, 5, 8]

Iterative Code

const selectionSort = (arr) => {
  for (let index = 0; index < arr.length; index++) {
    // Find the minimum element in the remaining unsorted array
    let minIndex = index;
    for (let j = index + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap elements
    [arr[index], arr[minIndex]] = [arr[minIndex], arr[index]];
  }
};

// Example usage
let arr = [5, 3, 8, 1, 2];
selectionSort(arr);
console.log(arr); // Output: [1, 2, 3, 5, 8]

Time Complexity - O(n²)

• Outer loop runs n times -> O(n) work.
• Inner loop finds min element → O(n) work.
• Total complexity: O(n) * O(n) = O(n²).

Space Complexity - O(1)

• No recursion.
• No extra data structures used.
• Only in-place swaps → O(1) space.

---

Key Differences Between Recursive & Iterative Approach

Approach	Time Complexity	Space Complexity	Technique
Recursive	O(n²)	O(n) (Call Stack)	Uses function calls
Iterative	O(n²)	O(1)	Uses loops

---

Final Thoughts

• Recursive Selection Sort is a conceptual way to understand sorting using recursion.
• Iterative Selection Sort is more efficient in terms of space (O(1)) and is preferable for real-world usage.
• Selection Sort is not optimal for large datasets due to its O(n²) time complexity.

---

Next Steps

• Try implementing Selection Sort in different languages.
• Compare Selection Sort vs. Bubble Sort vs. Insertion Sort.
• Optimize sorting using Merge Sort or Quick Sort.