Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that divides the input array into two parts: a sorted portion and an unsorted portion.

Algorithm Description

1. The algorithm maintains two subarrays:

   • Sorted subarray (initially empty)

   • Unsorted subarray (initially the entire input array)

2. Basic steps:

   • Find the minimum element in the unsorted subarray

   • Swap it with the first element of the unsorted subarray

   • Move the boundary between sorted and unsorted subarrays one element to the right

Implementation in Go

func selectionSort(arr []int) []int {
    n := len(arr)
    
    for i := 0; i < n-1; i++ {
        // Find minimum element in unsorted array
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        
        // Swap found minimum element with first element
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
    
    return arr
}

Time Complexity Analysis

Time Complexity: O(n²)

• The algorithm uses two nested loops

• Outer loop runs (n-1) times

• Inner loop runs (n-i-1) times for each i

• Total comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2

Space Complexity: O(1)

• Only uses a constant amount of extra space

• Sorting is done in-place

• Only needs space for temporary variable during swapping

Characteristics

Advantages

1. Simple implementation

2. Works well with small arrays

3. In-place sorting (no extra space needed)

4. Performs well when memory writing is costly

Disadvantages

1. O(n²) time complexity makes it inefficient for large arrays

2. Always performs O(n²) comparisons even if array is sorted

3. Not stable (relative order of equal elements may change)

Example Usage

package main

import "fmt"

func main() {
    // Example 1: Basic array
    arr1 := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Printf("Original array: %v\n", arr1)
    sorted1 := selectionSort(arr1)
    fmt.Printf("Sorted array: %v\n", sorted1)
    
    // Example 2: Array with duplicates
    arr2 := []int{5, 2, 8, 5, 1, 9, 2, 8}
    fmt.Printf("\nOriginal array: %v\n", arr2)
    sorted2 := selectionSort(arr2)
    fmt.Printf("Sorted array: %v\n", sorted2)
}

Output:

Original array: [64 34 25 12 22 11 90]
Sorted array: [11 12 22 25 34 64 90]

Original array: [5 2 8 5 1 9 2 8]
Sorted array: [1 2 2 5 5 8 8 9]

Related LeetCode Problems

Easy

1. 912. Sort an Array

   • Basic sorting implementation

   • Can be solved using Selection Sort (though not optimal for large inputs)

   • Time: O(n²), Space: O(1)

2. 977. Squares of a Sorted Array

   • Square elements and sort

   • Can use Selection Sort after squaring

   • Time: O(n²), Space: O(n)

3. 2160. Minimum Sum of Four Digit Number After Splitting Digits

   • Sort digits to minimize sum

   • Selection Sort works well for small fixed-size input

   • Time: O(1), Space: O(1)

Medium

1. 75. Sort Colors

   • Dutch National Flag problem

   • Can be solved with modified Selection Sort

   • Time: O(n²), Space: O(1)

2. 451. Sort Characters By Frequency

   • Count frequency and sort

   • Selection Sort on frequency array

   • Time: O(n + k²), Space: O(k) where k is character set size

3. 1329. Sort the Matrix Diagonally

   • Sort each diagonal

   • Selection Sort works well for small diagonals

   • Time: O(mnmin(m,n)), Space: O(min(m,n))

Hard

1. 1235. Maximum Profit in Job Scheduling

   • Sort jobs by start time

   • Selection Sort can be used but not optimal

   • Time: O(n²), Space: O(n)

Practice Tips

1. Start with Easy Problems:

   • Implement basic sorting

   • Handle edge cases

   • Consider input constraints

2. Medium Problems:

   • Modified Selection Sort

   • Combine with other techniques

   • Optimize for specific cases

3. Common Patterns:

   • Sort then process

   • Custom comparators

   • Partial sorting

4. Optimization Tips:

   • Consider input size

   • Look for problem-specific optimizations

   • Know when to use other sorting algorithms

Common Use Cases

1. Small arrays where simplicity is preferred

2. Educational purposes to learn sorting concepts

3. When auxiliary space is limited

4. When number of writes is a concern

Variations

1. Bidirectional Selection Sort

   • Finds both minimum and maximum in each pass

   • Slightly more efficient than basic version

2. Stable Selection Sort

   • Maintains relative order of equal elements

   • Uses more space or time to achieve stability

Best Practices

1. Use for small arrays (n < 50)

2. Consider other algorithms for larger datasets:

   • QuickSort for general purpose

   • MergeSort for guaranteed O(n log n)

   • HeapSort for in-place sorting

Related Algorithms

• Bubble Sort

• Insertion Sort

• QuickSort

• MergeSort

• HeapSort

Resources

1. Introduction to Algorithms (CLRS)

2. The Art of Computer Programming (Knuth)

3. Visualization

4. LeetCode Study Plan - Sorting