Selection Sort

Description

Selection Sort is a straightforward comparison-based sorting algorithm that operates on a simple yet effective principle: repeatedly selecting the smallest (or largest, depending on sorting order) element from the unsorted portion of the array and moving it to its correct position in the sorted portion. Despite its simplicity, understanding its mechanics provides valuable insight into fundamental sorting concepts.

The algorithm divides the input array into two conceptual regions: a sorted subarray that builds up from left to right, and an unsorted subarray that shrinks as the algorithm progresses. Initially, the sorted subarray is empty, and the entire array is considered unsorted. During each iteration, Selection Sort scans through the unsorted region to find the minimum element, then swaps it with the first element of the unsorted region. This process effectively expands the sorted region by one element while contracting the unsorted region by the same amount.

What distinguishes Selection Sort from other quadratic sorting algorithms is its consistency and minimal write operations. Unlike Bubble Sort, which may perform many swaps, Selection Sort performs exactly n-1 swaps for an array of n elements—one swap per iteration (except when the minimum element is already in the correct position). This makes it particularly useful when write operations are significantly more expensive than read operations, such as when working with flash memory or EEPROM storage.

However, this algorithm has a critical limitation: it always performs O(n²) comparisons regardless of the initial ordering of the data. Whether the array is already sorted, reverse sorted, or randomly arranged, Selection Sort will examine every element in the unsorted portion during each iteration. This lack of adaptability means it cannot take advantage of any existing order in the data, making it inefficient for large datasets or scenarios where the input might be partially sorted.

Another important characteristic is that Selection Sort is not stable. A stable sorting algorithm preserves the relative order of elements with equal values. Because Selection Sort swaps elements across potentially large distances in the array, it can inadvertently change the relative positions of equal elements, which may be undesirable when sorting complex objects by one of multiple fields.

How It Works

Selection Sort operates through a systematic process of partitioning the array into two conceptual regions and progressively building the sorted output. Understanding each step of this process is crucial to grasping how the algorithm achieves its sorting objective.

Visualization

Implementation

def selection_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        # Find the minimum element in remaining unsorted array
        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 first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# Usage example
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    selection_sort(arr)
    print("Sorted array:", arr)
                      

#include <iostream>
#include <vector>

class SelectionSort {
public:
    static void sort(std::vector<int>& arr) {
        int n = arr.size();
        
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            
            // Swap the found minimum element with the first element
            if (min_idx != i) {
                std::swap(arr[min_idx], arr[i]);
            }
        }
    }
};

// Usage example
int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    std::cout << "Original array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    SelectionSort::sort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}
                      

public class SelectionSort
{
    public static void Sort(int[] arr)
    {
        int n = arr.Length;
        
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n - 1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[min_idx])
                {
                    min_idx = j;
                }
            }
            
            // Swap the found minimum element with the first element
            if (min_idx != i)
            {
                (arr[min_idx], arr[i]) = (arr[i], arr[min_idx]);
            }
        }
    }
    
    // Usage example
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        Sort(arr);
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}
                      

Complexity Analysis

Advantages and Disadvantages