Selection Sort Algorithm

Selection sort is a simple comparison-based sorting algorithm that divides the array into sorted and unsorted portions. It repeatedly finds the minimum element from the unsorted portion and places it at the beginning of the sorted portion.

Interactive Visualization

Selection Sort Animation

Speed: 500ms

Array Visualization

Sorted Partition

Unsorted Partition

Sorted

Unsorted

Scanning

Minimum Found

Swapping

How Selection Sort Works:

• Find Minimum: Scan unsorted portion to find the smallest element

• Swap: Swap the minimum with the first element of unsorted portion

• Expand Sorted: The sorted portion grows by one element each iteration

• Time Complexity: O(n²) - always performs the same number of comparisons

• Space Complexity: O(1) - sorts in place

• Stability: Unstable - may change relative order of equal elements

How Selection Sort Works

Step-by-Step Process:

1. Find Minimum: Scan the unsorted portion to find the smallest element
2. Swap: Swap the minimum element with the first element of the unsorted portion
3. Expand Sorted: The sorted portion grows by one element
4. Repeat: Continue until the entire array is sorted

Key Characteristics:

• Always performs the same number of comparisons regardless of input
• Minimizes the number of swaps (at most n-1 swaps)
• Works by maintaining a sorted and unsorted partition
• Not adaptive - doesn't benefit from pre-sorted data

Pseudocode

ALGORITHM SelectionSort(arr[])
BEGIN
    n = length of arr
    
    FOR i = 0 TO n-2 DO
        minIndex = i
        
        // Find minimum element in unsorted portion
        FOR j = i+1 TO n-1 DO
            IF arr[j] < arr[minIndex] THEN
                minIndex = j
            END IF
        END FOR
        
        // Swap minimum with first unsorted element
        IF minIndex ≠ i THEN
            SWAP arr[i] WITH arr[minIndex]
        END IF
    END FOR
END

Complexity Analysis

Metric	Best Case	Average Case	Worst Case
Time Complexity	O(n²)	O(n²)	O(n²)
Space Complexity	O(1)	O(1)	O(1)
Number of Swaps	0	O(n)	O(n)

Note: Selection sort always performs O(n²) comparisons, making it inefficient for large datasets, but it minimizes the number of swaps which can be beneficial when write operations are expensive.

Code Examples

Here are implementations of selection sort in different programming languages. Each version demonstrates the same algorithm with language-specific syntax and conventions.

 def selection_sort(arr):
    """
    Sort an array using the selection sort algorithm.
    Time Complexity: O(n²)
    Space Complexity: O(1)
    """
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n - 1):
        # Find the minimum element in the remaining unsorted array
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Swap the found minimum element with the first element
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

# Example usage
if __name__ == "__main__":
    numbers = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", numbers)
    selection_sort(numbers)
    print("Sorted array:", numbers) 
 public class SelectionSort {
    
    /**
     * Sorts an array using the selection sort algorithm
     * @param arr The array to be sorted
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // Move boundary of unsorted subarray one by one
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted array
            int minIndex = i;
            for (int 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) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
    
    /**
     * Helper method to print an array
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.print("Original array: ");
        printArray(numbers);
        
        selectionSort(numbers);
        
        System.out.print("Sorted array: ");
        printArray(numbers);
    }
} 
 #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * Sorts a vector using the selection sort algorithm
 * @param arr Reference to the vector to be sorted
 */
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    
    // Move boundary of unsorted subarray one by one
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted array
        int minIndex = i;
        for (int 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) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

/**
 * Helper function to print a vector
 */
void printArray(const vector<int>& arr) {
    for (int value : arr) {
        cout << value << " ";
    }
    cout << endl;
}

int main() {
    vector<int> numbers = {64, 34, 25, 12, 22, 11, 90};
    
    cout << "Original array: ";
    printArray(numbers);
    
    selectionSort(numbers);
    
    cout << "Sorted array: ";
    printArray(numbers);
    
    return 0;
} 

When to Use Selection Sort

Advantages

• Simple: Easy to understand and implement
• In-place: Requires only O(1) extra memory
• Minimal swaps: Performs at most n-1 swaps
• Consistent: Always O(n²) time complexity

Disadvantages

• Inefficient: O(n²) time complexity for all cases
• Not adaptive: Doesn't benefit from sorted data
• Unstable: May change relative order of equal elements
• Poor for large datasets: Not suitable for big data

Good For: Educational purposes, small datasets (n < 50), when memory is limited, when number of swaps must be minimized

Avoid For: Large datasets, performance-critical applications, when stability is required, real-time systems