Selection Sort

How It Works?

• Compares each element in the unsorted portion to find the minimum element.
• Swaps the minimum element with the first element of the unsorted portion.
• Moves the boundary of the sorted portion one element forward.
• Repeats this process until the entire list is sorted.

Selection Sort Insight

Selection sort is not the most efficient algorithm for large lists, but it is easy to understand and implement. It performs well on small lists and has the advantage of making at most n-1 swaps, which can be useful when memory write operations are costly.

Implementation

JavaScript

function selectionSort(array) {
  const n = array.length;

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

    for (let j = i + 1; j < n; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }

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

  return array;
}

console.log(selectionSort([99, 44, 6, 2, 1, 5]));
// Output: [1, 2, 5, 6, 44, 99]

Python

def selectionSort(array):
  n = len(array)

  for i in range(n - 1):
      minIndex = i

      for j in range(i + 1, n):
          if array[j] < array[minIndex]:
              minIndex = j

      if minIndex != i:
          array[i], array[minIndex] = array[minIndex], array[i]

  return array

print(selectionSort([99, 44, 6, 2, 1, 5]))
# Output: [1, 2, 5, 6, 44, 99]

Complexity and Features

• Time Complexity:
  • O(n²) for average and worst cases
  • O(n²) for best case as well, since it always scans the remaining elements to find the minimum.
• Space Complexity: O(1) because it sorts in-place without extra memory.
• Stable: No, equal elements may not retain their original order.
• Number of Swaps: At most n-1, which is beneficial when memory write operations are costly.