Common Mistakes in Selection Sort and How to Avoid Them

Selection sort, while simple in concept, can be tricky to implement correctly. Whether you’re new to coding or just need a refresher, it’s easy to make common mistakes. In this article, we’ll explore the common pitfalls in selection sort and provide clear solutions to avoid them. By the end, you’ll be able to write a correct and efficient selection sort implementation.

Incorrect Loop Boundaries

One of the most common mistakes in selection sort is setting up the loop boundaries incorrectly. This can lead to the algorithm skipping elements or causing out-of-bounds errors.

Mistake:

def selection_sort(arr):
  n = len(arr)
  for i in range(n):  # Incorrect range
    min_idx = i
    for j in range(i + 1, n + 1):  # Incorrect range
      if arr[j] < arr[min_idx]:
        min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

Why It’s Wrong:

  • The outer loop for i in range(n) iterates one time too many. Since selection sort works by finding the minimum element in the unsorted portion and placing it at the beginning, the last element will automatically be in the correct position after the n-1 element is sorted. Iterating through all n elements will lead to an out-of-bounds error in the inner loop.
  • The inner loop for j in range(i + 1, n + 1) also iterates one time too many, causing an IndexError: list index out of range because it tries to access arr[n] which is beyond the list’s bounds.

Fix:

Ensure the outer loop goes up to n - 1 and the inner loop goes up to n.

def selection_sort(arr):
  n = len(arr)
  for i in range(n - 1):  # Correct range
    min_idx = i
    for j in range(i + 1, n):  # Correct range
      if arr[j] < arr[min_idx]:
        min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

Forgetting to Update min_idx

Another frequent mistake is failing to update the min_idx variable when a smaller element is found in the inner loop. This results in incorrect swaps and an unsorted array.

Mistake:

def selection_sort(arr):
  n = len(arr)
  for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
      if arr[j] < arr[i]:  # Incorrect comparison
        min_idx = j # forgot to update min_idx here
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

Why It’s Wrong:

  • The condition if arr[j] < arr[i] compares elements against arr[i] instead of arr[min_idx]. Therefore, the code always compares against the first element of the unsorted portion instead of the smallest element found so far.

Fix:

Always compare against arr[min_idx] to ensure you’re tracking the smallest element correctly.

def selection_sort(arr):
  n = len(arr)
  for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
      if arr[j] < arr[min_idx]:  # Correct comparison
        min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

Swapping with the Same Element

A subtle mistake is swapping an element with itself, which, while not causing an error, is unnecessary and reduces efficiency.

Mistake:

def selection_sort(arr):
  n = len(arr)
  for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
      if arr[j] < arr[min_idx]:
        min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]  # Always swaps, even when i == min_idx

Why It’s Unnecessary:

  • If min_idx is equal to i, the swap operation arr[i], arr[min_idx] = arr[min_idx], arr[i] swaps the element with itself, which has no effect.

Fix:

Add a check to ensure the swap only occurs when min_idx and i are different.

def selection_sort(arr):
  n = len(arr)
  for i in range(n - 1):
    min_idx = i
    for j in range(i + 1, n):
      if arr[j] < arr[min_idx]:
        min_idx = j
    if min_idx != i:  # Only swap when necessary
      arr[i], arr[min_idx] = arr[min_idx], arr[i]

Key Takeaways

  1. Correct Loop Ranges: Use range(n - 1) for the outer loop and range(i + 1, n) for the inner loop.
  2. Update min_idx Properly: Always compare against arr[min_idx] and update min_idx when a smaller element is found.
  3. Avoid Unnecessary Swaps: Check if min_idx != i before swapping.

By avoiding these common mistakes, you can write a correct and efficient selection sort implementation.

What’s Next?

Now that you understand common mistakes in selection sort implementation, you might want to explore: