Selection Sort Implementation

JavaScript Implementation

function selectionSort(arr) {
  const n = arr.length;
  
  // Iterate through the array
  for (let i = 0; i < n - 1; i++) {
    // Find the minimum element in the unsorted array
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // Swap the found minimum element with the first element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

// Usage example
let array = [64, 25, 12, 22, 11];
console.log(selectionSort(array)); // [11, 12, 22, 25, 64]

Python Implementation

def selection_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n - 1):
        # Find the minimum element in the unsorted part
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap the found minimum element with the element at position i
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# Test
array = [64, 25, 12, 22, 11]
print(selection_sort(array))  # [11, 12, 22, 25, 64]

Key Implementation Details:

• Minimum Element Finding: The inner loop's only purpose is to find the position of the minimum element in the unsorted portion.
• Conditional Swap: The algorithm only performs a swap if the minimum element is not already in the correct position (when minIndex !== i), which can save some unnecessary swaps.
• In-place Sorting: The sort is performed directly on the input array without requiring additional space for the main sorting operation.
• Minimal Swaps: Selection sort performs at most n-1 swaps, which is minimal among comparison-based sorting algorithms.

Optimization Tips:

• Early Termination: Unlike bubble sort, selection sort cannot be optimized with an early termination condition since it always needs to scan the entire unsorted portion.
• Bidirectional Selection Sort: A variation called "bidirectional selection sort" can find both the minimum and maximum elements in each pass, reducing the number of passes needed by roughly half.