Selection Sort

Visual Example

Let's sort the array [64, 25, 12, 22, 11] using selection sort:

Initial array: [64, 25, 12, 22, 11]

First pass:
- Find minimum in [64, 25, 12, 22, 11]: 11 at index 4
- Swap 64 and 11: [11, 25, 12, 22, 64]
- Sorted region: [11] | Unsorted region: [25, 12, 22, 64]

Second pass:
- Find minimum in [25, 12, 22, 64]: 12 at index 2
- Swap 25 and 12: [11, 12, 25, 22, 64]
- Sorted region: [11, 12] | Unsorted region: [25, 22, 64]

Third pass:
- Find minimum in [25, 22, 64]: 22 at index 1
- Swap 25 and 22: [11, 12, 22, 25, 64]
- Sorted region: [11, 12, 22] | Unsorted region: [25, 64]

Fourth pass:
- Find minimum in [25, 64]: 25 at index 0
- No swap needed (already in place)
- Sorted region: [11, 12, 22, 25] | Unsorted region: [64]

Final pass:
- Only one element left in unsorted region, so we're done
- Final sorted array: [11, 12, 22, 25, 64]

C++ Implementation

#include <iostream>
#include <vector>

std::vector<int> selectionSort(std::vector<int> arr) {
    int n = arr.size();
    
    // Traverse through all array elements
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in remaining unsorted array
        int min_index = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        
        // Swap the found minimum element with the first element
        if (min_index != i) {
            std::swap(arr[i], arr[min_index]);
        }
    }
    
    return arr;
}

int main() {
    std::vector<int> array = {64, 25, 12, 22, 11};
    std::vector<int> sorted = selectionSort(array);
    
    // Print the sorted array
    for (int num : sorted) {
        std::cout << num << " ";
    }
    // Output: 11 12 22 25 64
    
    return 0;
}

Space Complexity

• Space Complexity: O(1) - Selection sort is an in-place sorting algorithm that doesn't require any extra space proportional to the input size
• Only a few extra variables are needed regardless of the array size

Example of Instability

Consider sorting an array of objects with keys and values:

Initial array: [(4,1), (3,2), (4,3), (2,4)]
                   ^           ^
                These two elements have the same key (4)

After selection sort:
[(2,4), (3,2), (4,1), (4,3)]
                  ^      ^
            The relative order of these equal elements changed

In the original array, (4,1) appeared before (4,3), but after sorting, the order might be reversed, depending on the implementation.

It is possible to implement a stable version of selection sort, but it typically requires additional space or more complex logic.

2. Stable Selection Sort

A modified version of selection sort that preserves the relative order of equal elements.

function stableSelectionSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    // Find minimum element
    let minIndex = i;
    
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // If the minimum is not the current element
    if (minIndex !== i) {
      // Save the minimum value
      const minValue = arr[minIndex];
      
      // Shift all elements between i and minIndex by one position
      for (let k = minIndex; k > i; k--) {
        arr[k] = arr[k - 1];
      }
      
      // Place the minimum at position i
      arr[i] = minValue;
    }
  }
  
  return arr;
}

This stable version uses more operations (specifically, more assignments) but preserves the relative order of equal elements by shifting elements rather than swapping them.