18.1 — Sorting an array using selection sort

In this lesson, you'll learn about sorting algorithms by implementing selection sort, one of the simplest and most intuitive sorting algorithms. This will lay the foundation for understanding algorithms and their analysis.

What is sorting?

Sorting is the process of arranging elements in a specific order, typically ascending (smallest to largest) or descending (largest to smallest). Sorting is one of the most fundamental operations in computer science.

Think of sorting like organizing items in real life:

• Arranging books on a shelf by title or author
• Organizing cards in a card game by value
• Putting receipts in chronological order
• Ranking students by their test scores

Why is sorting important?

Sorting is crucial because:

1. Search efficiency: Finding items in sorted data is much faster
2. Data presentation: Users expect organized information
3. Algorithm foundations: Many algorithms work better with sorted data
4. Database operations: Sorted data enables efficient database queries
5. Problem solving: Many problems become easier with sorted input

Introduction to selection sort

Selection sort is one of the simplest sorting algorithms to understand. It works by:

1. Finding the smallest element in the unsorted portion
2. Swapping it with the first unsorted element
3. Moving the boundary between sorted and unsorted portions
4. Repeating until the entire array is sorted

Here's a visual example with the array [64, 25, 12, 22, 11]:

Initial:  [64, 25, 12, 22, 11]
Step 1:   [11, 25, 12, 22, 64]  // Found min (11), swapped with first (64)
Step 2:   [11, 12, 25, 22, 64]  // Found min (12), swapped with second (25)
Step 3:   [11, 12, 22, 25, 64]  // Found min (22), swapped with third (25)
Step 4:   [11, 12, 22, 25, 64]  // Found min (25), already in position
Final:    [11, 12, 22, 25, 64]  // Array is sorted!

Implementing selection sort

Let's implement selection sort step by step:

#include <iostream>
#include <vector>

void selectionSort(std::vector<int>& arr)
{
    int n = arr.size();
    
    // Move boundary of unsorted subarray
    for (int i = 0; i < n - 1; ++i)
    {
        // Find the minimum element in remaining 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)
        {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

void printArray(const std::vector<int>& arr)
{
    for (int element : arr)
    {
        std::cout << element << " ";
    }
    std::cout << std::endl;
}

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

Output:

Original array: 64 25 12 22 11 
Sorted array: 11 12 22 25 64 

Let's break down the algorithm:

1. Outer loop (i from 0 to n-2): Represents the boundary between sorted and unsorted portions
2. Inner loop (j from i+1 to n-1): Finds the minimum element in the unsorted portion
3. Swap operation: Places the minimum element at the correct position

Tracing through the algorithm

Let's trace through selection sort with a detailed step-by-step example:

#include <iostream>
#include <vector>

void selectionSortDetailed(std::vector<int>& arr)
{
    int n = arr.size();
    std::cout << "Starting selection sort with array: ";
    for (int element : arr)
        std::cout << element << " ";
    std::cout << std::endl << std::endl;
    
    for (int i = 0; i < n - 1; ++i)
    {
        std::cout << "Step " << (i + 1) << ":" << std::endl;
        std::cout << "Looking for minimum in unsorted portion starting at index " << i << std::endl;
        
        int minIndex = i;
        int minValue = arr[i];
        
        for (int j = i + 1; j < n; ++j)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
                minValue = arr[j];
                std::cout << "  New minimum found: " << minValue << " at index " << j << std::endl;
            }
        }
        
        if (minIndex != i)
        {
            std::cout << "  Swapping " << arr[i] << " (index " << i << ") with " << arr[minIndex] << " (index " << minIndex << ")" << std::endl;
            std::swap(arr[i], arr[minIndex]);
        }
        else
        {
            std::cout << "  No swap needed - minimum is already in correct position" << std::endl;
        }
        
        std::cout << "  Array after step " << (i + 1) << ": ";
        for (int element : arr)
            std::cout << element << " ";
        std::cout << std::endl << std::endl;
    }
}

int main()
{
    std::vector<int> numbers = {64, 25, 12, 22, 11};
    selectionSortDetailed(numbers);
    
    std::cout << "Final sorted array: ";
    for (int element : numbers)
        std::cout << element << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Starting selection sort with array: 64 25 12 22 11 

Step 1:
Looking for minimum in unsorted portion starting at index 0
  New minimum found: 25 at index 1
  New minimum found: 12 at index 2
  New minimum found: 11 at index 4
  Swapping 64 (index 0) with 11 (index 4)
  Array after step 1: 11 25 12 22 64 

Step 2:
Looking for minimum in unsorted portion starting at index 1
  New minimum found: 12 at index 2
  Swapping 25 (index 1) with 12 (index 2)
  Array after step 2: 11 12 25 22 64 

Step 3:
Looking for minimum in unsorted portion starting at index 2
  New minimum found: 22 at index 3
  Swapping 25 (index 2) with 22 (index 3)
  Array after step 3: 11 12 22 25 64 

Step 4:
Looking for minimum in unsorted portion starting at index 3
  No swap needed - minimum is already in correct position
  Array after step 4: 11 12 22 25 64 

Final sorted array: 11 12 22 25 64 

Selection sort with different data types

Selection sort works with any comparable data type. Here's an example with strings:

#include <iostream>
#include <vector>
#include <string>

void selectionSort(std::vector<std::string>& arr)
{
    int n = arr.size();
    
    for (int i = 0; i < n - 1; ++i)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (arr[j] < arr[minIndex]) // String comparison is lexicographic
            {
                minIndex = j;
            }
        }
        
        if (minIndex != i)
        {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

int main()
{
    std::vector<std::string> names = {"David", "Alice", "Charlie", "Bob", "Eve"};
    
    std::cout << "Original names: ";
    for (const std::string& name : names)
        std::cout << name << " ";
    std::cout << std::endl;
    
    selectionSort(names);
    
    std::cout << "Sorted names: ";
    for (const std::string& name : names)
        std::cout << name << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Original names: David Alice Charlie Bob Eve 
Sorted names: Alice Bob Charlie David Eve 

Algorithm analysis: Time and space complexity

Understanding algorithm complexity helps you choose the right algorithm for your needs:

Time complexity

• Best case: O(n²) - Even if the array is already sorted, we still check all elements
• Average case: O(n²) - On average, we perform n²/2 comparisons
• Worst case: O(n²) - Maximum number of comparisons is n(n-1)/2

Space complexity

• O(1) - Selection sort is an "in-place" algorithm, using only a constant amount of extra memory

Comparison count example

For an array of n elements, selection sort makes:

• First pass: n-1 comparisons
• Second pass: n-2 comparisons
• Third pass: n-3 comparisons
• ...
• Last pass: 1 comparison

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

#include <iostream>
#include <vector>

int selectionSortWithCount(std::vector<int>& arr)
{
    int n = arr.size();
    int comparisons = 0;
    
    for (int i = 0; i < n - 1; ++i)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
        {
            comparisons++; // Count each comparison
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        
        if (minIndex != i)
        {
            std::swap(arr[i], arr[minIndex]);
        }
    }
    
    return comparisons;
}

int main()
{
    std::vector<int> numbers = {64, 25, 12, 22, 11};
    int n = numbers.size();
    
    std::cout << "Array size: " << n << std::endl;
    std::cout << "Theoretical comparisons: " << n * (n - 1) / 2 << std::endl;
    
    int actualComparisons = selectionSortWithCount(numbers);
    std::cout << "Actual comparisons: " << actualComparisons << std::endl;
    
    return 0;
}

Output:

Array size: 5
Theoretical comparisons: 10
Actual comparisons: 10

When to use selection sort

Advantages:

• Simple to understand and implement
• Performs well on small datasets
• In-place sorting (uses O(1) extra memory)
• Unstable but consistent performance
• Minimizes the number of swaps (at most n-1 swaps)

Disadvantages:

• O(n²) time complexity makes it inefficient for large datasets
• Not adaptive - doesn't take advantage of existing order
• Not stable - doesn't preserve relative order of equal elements

Best use cases:

• Small arrays (typically n < 50)
• When memory is limited
• When the cost of swapping is high
• Educational purposes to understand sorting concepts

Comparison with other sorting algorithms

Here's how selection sort compares to other common sorting algorithms:

Common mistakes and best practices

Common mistakes:

1. Off-by-one errors in loop bounds
2. Unnecessary swaps when minIndex equals i
3. Modifying the array while iterating incorrectly

Best practices:

1. Check for unnecessary swaps before swapping
2. Use descriptive variable names (minIndex instead of k)
3. Add bounds checking for production code
4. Consider using standard library algorithms for real applications

Enhanced selection sort with bounds checking

#include <iostream>
#include <vector>
#include <stdexcept>

void selectionSortSafe(std::vector<int>& arr)
{
    if (arr.empty())
    {
        return; // Nothing to sort
    }
    
    size_t n = arr.size();
    
    for (size_t i = 0; i < n - 1; ++i)
    {
        size_t minIndex = i;
        
        for (size_t j = i + 1; j < n; ++j)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        
        // Only swap if necessary
        if (minIndex != i)
        {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

int main()
{
    // Test with various cases
    std::vector<std::vector<int>> testCases = {
        {},                    // Empty array
        {42},                  // Single element
        {3, 1, 4, 1, 5},      // Multiple elements with duplicates
        {5, 4, 3, 2, 1},      // Reverse sorted
        {1, 2, 3, 4, 5}       // Already sorted
    };
    
    for (size_t i = 0; i < testCases.size(); ++i)
    {
        auto test = testCases[i];
        std::cout << "Test case " << (i + 1) << " - Original: ";
        for (int element : test)
            std::cout << element << " ";
        std::cout << std::endl;
        
        selectionSortSafe(test);
        
        std::cout << "Test case " << (i + 1) << " - Sorted: ";
        for (int element : test)
            std::cout << element << " ";
        std::cout << std::endl << std::endl;
    }
    
    return 0;
}

Output:

Test case 1 - Original: 
Test case 1 - Sorted: 

Test case 2 - Original: 42 
Test case 2 - Sorted: 42 

Test case 3 - Original: 3 1 4 1 5 
Test case 3 - Sorted: 1 1 3 4 5 

Test case 4 - Original: 5 4 3 2 1 
Test case 4 - Sorted: 1 2 3 4 5 

Test case 5 - Original: 1 2 3 4 5 
Test case 5 - Sorted: 1 2 3 4 5 

Summary

Selection sort is an excellent introduction to sorting algorithms because:

• Simple logic: Find the minimum, swap it to the correct position, repeat
• Predictable performance: Always O(n²) time complexity
• Minimal memory usage: Only O(1) extra space required
• Educational value: Teaches fundamental sorting concepts
• Foundation knowledge: Prepares you for more complex algorithms

While selection sort isn't efficient for large datasets, understanding it helps you:

• Appreciate the importance of algorithm efficiency
• Understand the trade-offs between simplicity and performance
• Build intuition for more advanced sorting algorithms
• Learn algorithm analysis techniques

In the next lesson, you'll learn about iterators, which provide a more elegant way to traverse and manipulate collections of data.

Quiz

1. What is the time complexity of selection sort in the best, average, and worst cases?
2. Why does selection sort make the same number of comparisons regardless of input order?
3. What is the maximum number of swaps selection sort will perform for an array of n elements?
4. Is selection sort a stable sorting algorithm? Why or why not?
5. When might selection sort be preferable to more efficient algorithms like merge sort?

Practice exercises

Try these exercises to deepen your understanding of selection sort:

1. Descending selection sort: Modify selection sort to sort an array in descending order instead of ascending order.

2. Selection sort with custom comparison: Implement selection sort that can sort an array of structs representing students by their grades.

3. Performance comparison: Write a program that compares the performance of selection sort on arrays that are already sorted, reverse sorted, and randomly arranged.

4. Selection sort variants: Implement "bidirectional selection sort" that finds both the minimum and maximum in each pass, placing them at both ends of the unsorted portion.