Mr Punk da Silva

Posted on Jun 25

Understanding Selection Sort

#programming #tutorial #algorithms

What is Selection Sort?

The Selection Sort is a simple and intuitive sorting algorithm that works by dividing the array into two parts:

Sorted part: Located at the beginning of the array (initially empty).
Unordered part: Located at the end of the array (initially the whole array)

How does it work?

The algorithm works as follows:

Finds the smallest element of the unsorted part
Exchanges this element with the first element of the unsorted part
Expand the sorted part by one position
**Repeat the process until the entire array is sorted

Diagramming

Visual Example

Considering the array: [64, 25, 12, 22, 11]

Iteration 1:

Sorted part: []
Unordered part: [64, 25, 12, 22, 11]
Smallest element: 11 (position 4)
Swap: 11 ↔ 64
Result: [11, 25, 12, 22, 64]

Iteration 2:

Sorted part: [11]
Unordered part: [25, 12, 22, 64]
Smallest element: 12 (position 2)
Swap: 12 ↔ 25
Result: [11, 12, 25, 22, 64]

Iteration 3:

Sorted part: [11, 12]
Unordered part: [25, 22, 64]
Smallest element: 22 (position 3)
Swap: 22 ↔ 25
Result: [11, 12, 22, 25, 64]

Iteration 4:

Sorted part: [11, 12, 22]
Unordered part: [25, 64]
Smallest element: 25 (already in the correct position)
No swap required
Result: [11, 12, 22, 25, 64]

Implementation

Our educational implementation includes detailed outputs to help you learn.

You can find a complete and educational implementation of Selection Sort at:

📁 Domus/Domus-1/selectionSort.cpp

Main Function - Selection Sort Algorithm

void selectionSortAlgorithm(int dataArray[], int arraySize)
{
    cout << "========================================" << endl;
    cout << "STARTING SELECTION SORT ALGORITHM" << endl;
    cout << "========================================" << endl;
    cout << "Initial array: ";
    for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
        cout << dataArray[displayIndex] << " ";
    }
    cout << endl << endl;

    int totalNumberOfSwaps = 0;

    for (int currentPosition = 0; currentPosition < arraySize - 1; currentPosition++)
    {
        cout << ">>> ITERATION " << (currentPosition + 1) << " <<<" << endl;
        cout << "Looking for smallest element for position " << currentPosition << endl;

        int smallestElementIndex = findSmallestElementIndex(dataArray, currentPosition, arraySize - 1);

        if (currentPosition != smallestElementIndex) {
            cout << "Smallest element is at position " << smallestElementIndex << ", need to swap with position " << currentPosition << endl;
            swapElements(dataArray, currentPosition, smallestElementIndex);
            totalNumberOfSwaps++;
        } else {
            cout << "Smallest element is already in correct position (" << currentPosition << "), no swap needed" << endl;
        }

        cout << "Array state after iteration " << (currentPosition + 1) << ": ";
        for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
            if (displayIndex <= currentPosition) {
                cout << "[" << dataArray[displayIndex] << "] "; // Already sorted elements
            } else {
                cout << dataArray[displayIndex] << " ";        // Not yet sorted elements
            }
        }
        cout << endl;
        cout << "Elements sorted: " << (currentPosition + 1) << "/" << arraySize << endl;
        cout << "--------------------------------" << endl;
    }

    cout << "========================================" << endl;
    cout << "SELECTION SORT ALGORITHM COMPLETED!" << endl;
    cout << "Total number of swaps performed: " << totalNumberOfSwaps << endl;
    cout << "========================================" << endl;
}

Function to Find the Smallest Element

int findSmallestElementIndex(int dataArray[], int startIndex, int endIndex)
{
    cout << "--- Searching for smallest element in range [" << startIndex << ", " << endIndex << "] ---" << endl;
    int currentIndex = startIndex;
    int smallestIndex = currentIndex;
    int numberOfComparisons = 0;

    cout << "Initial element for comparison: dataArray[" << smallestIndex << "] = " << dataArray[smallestIndex] << endl;

    while (currentIndex <= endIndex)
    {
        cout << "Comparing dataArray[" << currentIndex << "] = " << dataArray[currentIndex] << " with current smallest dataArray[" << smallestIndex << "] = " << dataArray[smallestIndex];
        numberOfComparisons++;

        if (dataArray[currentIndex] < dataArray[smallestIndex])
        {
            cout << " -> " << dataArray[currentIndex] << " is smaller! New smallest element found at position " << currentIndex << endl;
            smallestIndex = currentIndex;
        }
        else
        {
            cout << " -> " << dataArray[currentIndex] << " >= " << dataArray[smallestIndex] << ", keeping current smallest" << endl;
        }

        currentIndex++;
    }

    cout << "Smallest element found: " << dataArray[smallestIndex] << " at position " << smallestIndex << " (after " << numberOfComparisons << " comparisons)" << endl;
    return smallestIndex;
}

Função para Trocar Elementos

void swapElements(int dataArray[], int firstPosition, int secondPosition)
{
    cout << "  -> Swapping elements: " << dataArray[firstPosition] << " (position " << firstPosition << ") <-> " << dataArray[secondPosition] << " (position " << secondPosition << ")" << endl;
    int temporaryValue = dataArray[firstPosition];
    dataArray[firstPosition] = dataArray[secondPosition];
    dataArray[secondPosition] = temporaryValue;
    cout << "  -> After swap: position " << firstPosition << " = " << dataArray[firstPosition] << ", position " << secondPosition << " = " << dataArray[secondPosition] << endl;
}

Algorithm Characteristics

Time Complexity

Best case O(n²) - Even if the array is already sorted
Average case**: O(n²) - Typical behavior
Worst case**: O(n²) - Inversely sorted array

Space Complexity

O(1) - In-place algorithm, uses only additional constant memory

Important Properties

Property	Value
Stable	❌ No
In-place	✅ Yes
Adaptive	❌ No
Comparisons	O(n²)
Exchanges	O(n)

Why is Selection Sort NOT Stable?

What does "Stability" mean in sorting algorithms?

A sorting algorithm is stable when it maintains the relative order of elements that have equal values. In other words, if two elements have the same value, the one that appears first in the original array must appear first in the sorted array.

Practical example of instability

Consider an array of cards where each card has a value and a suit:

Initial array: [5♠, 3♦, 5♥, 2♣, 3♠]

Let's sort by numerical value only, ignoring the suit:

✅ Stable ordering (expected):

[2♣, 3♦, 3♠, 5♠, 5♥]

Note that 3♦ comes before 3♠ (maintains original order)
And 5♠ comes before 5♥ (retains original order)

❌ Selection Sort (unstable):

[2♣, 3♠, 3♦, 5♥, 5♠]

3♠ now comes before 3♦ (order changed!)
5♥ now comes before 5♠ (order changed!)

Why does this happen in Selection Sort?

The Selection Sort swaps elements that are far apart, which can "jump" over equal elements and change their relative order.

Demonstration with simple numbers:

Starting array: [4, 2, 4, 1, 3]

To distinguish, let's call it: [4a, 2, 4b, 1, 3]

Selection Sort execution:

Iteration 1:

Finds smallest element: 1 (position 3)
Exchange: 4a ↔ 1
Result: [1, 2, 4b, 4a, 3]

Note:** 4b now comes before 4a!

Iteration 2:

Smaller search in the unordered part [2, 4b, 4a, 3]: 2 is already correct
No swap
Result: [1, 2, 4b, 4a, 3]

Iteration 3:

Search smaller in unordered part [4b, 4a, 3]: 3 (position 4)
Exchange: 4b ↔ 3
Result: [1, 2, 3, 4a, 4b]

Final array: [1, 2, 3, 4a, 4b]

The "Far Exchange" Problem

Array: [4a, 2, 4b, 1, 3]
 ↑
 |___________|
 Far swap that "jumps"
 over 4b, changing the order!

When the Selection Sort finds the smallest element in a distant position, it swaps it directly with the current position, jumping over all intermediate elements, including those with the same value.

Practical Impact of Instability

Instability can be problematic in real-life situations:

**Sorting employee records by salary.
- If two employees have the same salary, you may want to keep the original order (e.g. by hire date).
**Sorting products by price
- Products with the same price can have different display priorities
Sorting student grades:
- Students with the same grade can initially be in alphabetical order

How can I make the Selection Sort stable?

It is possible to modify the Selection Sort to be stable, but this increases the complexity:

// Stable version (less efficient)
void stableSelectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }

         // Instead of swapping directly, 
        // shifts all elements between i and minIdx
        int key = arr[minIdx];
        while (minIdx > i) {
            arr[minIdx] = arr[minIdx-1];
            minIdx--;
        }
        arr[i] = key;
    }
}

But this increases the complexity of switching from O(n) to O(n²)!

Visualization of Instability - "Rotation"

The concept of "rotation" that you mentioned refers to the way the elements "rotate" or change their relative positions during distant exchanges:

Initial state: [4a, 2, 4b, 1, 3]
 ▲ ▲
 └──────────────┘ Far swap in iteration 1

After exchange: [1, 2, 4b, 4a, 3]
 ▲ ▲
 4b "rotated" in front of 4a

Initial state: [A, B, C, D] (where A = D in value)
After Selection: [D, B, C, A] (A and D have swapped positions!)
 ▲ ▲
 └────────┘ "Rotation" - relative order reversed

Visual comparison: Stable vs Unstable

Stable Algorithm (e.g. Insertion Sort):

[3a, 1, 3b, 2] → [1, 2, 3a, 3b] ✅ Order maintained
 ▲ ▲ ▲ ▲
 └──────┘ └───┘ 3a still comes before 3b

Selection Sort (Unstable)

[3a, 1, 3b, 2] → [1, 2, 3b, 3a] ❌ Order changed!
 ▲ ▲ ▲
 └──────┘ └───┘ 3b now comes before 3a

Summary: Why Selection Sort is Unstable

Distant swaps: Elements are swapped over large distances
Skips elements: Ignores equal elements halfway through
Focuses on value only: Does not consider the original position of equal elements
Prioritizes efficiency: The stable version would be much less efficient
Rotativity: Equal elements can "rotate" their positions

Advantages vs. Disadvantages

Advantages

Simple to implement and understand

✅ Few exchanges: Maximum of n-1 exchanges In-place: No additional memory required
Works well with small arrays** Efficient when write operations are expensive

Disadvantages

❌ Complexity O(n²): Inefficient for large arrays Not stable: Can change the relative order of equal elements Not adaptive: Does not take advantage of partially ordered arrays
❌ Always makes n-1 passes: Even if the array is already sorted

When to use it?

Selection Sort is suitable when:

Small arrays (< 50 elements)
Writing operations are expensive (e.g. flash memory)
Simplicity is more important than efficiency
Memory is limited (in-place algorithm)

Comparison with Other Algorithms

Algorithm	Best Case	Average Case	Worst Case	Stable	Swaps
Selection Sort	O(n²)	O(n²)	❌	O(n)
Bubble Sort	O(n)	O(n²)	O(n²)	✅	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)	✅	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	✅	-
Quick Sort	O(n log n)	O(n log n)	O(n²)	❌	O(n log n)

Variations of the Selection Sort

1. Bidirectional Selection Sort

Simultaneously finds the smallest and largest element in each pass, placing them at the ends.

2. recursive selection sort

Recursive implementation that recursively sorts the subarray after placing the smallest element in the first position.

Stable Selection Sort

Modification that maintains stability by changing elements only when necessary.

Practical Exercises

Exercise 1: Basic Implementation

Implement Selection Sort to sort an array of strings in alphabetical order.

💡 Solution to Exercise 1

Code

**Important points

We use the < operator for lexicographic string comparison
The logic is the same as Selection Sort for numbers
Strings are sorted alphabetically (A-Z)

Exercise 2: Counting Operations

Modify the algorithm to count the number of comparisons and exchanges made.

💡 Solution to Exercise 2

Code

**Analysis of Statistics

Comparisons: Always n(n-1)/2 regardless of input
Swaps: Maximum n-1, can be smaller if some elements are already in place
Efficiency: Shows how many exchanges were actually necessary

Exercise 3: Stable Version

Implement a stable version of the Selection Sort.

💡 Solution to Exercise 3

Code

**How the stable version works

Rotation instead of swapping: Instead of swapping the smallest element with the first, we rotate all the elements
Relative order preserved: Equal elements keep their original order
Complexity: O(n²) time, but O(n) movement operations per iteration
Trade-off: More movement operations, but maintains stability

**Visual difference

Normal Selection Sort: [2a, 2b] → [2b, 2a] (not stable)
Stable Selection Sort: [2a, 2b] → [2a, 2b] (stable)

Conclusion

The Selection Sort is an excellent algorithm for learning the concepts of sorting due to its simplicity and intuitive logic. Although it is not efficient for large arrays, it has its place in specific situations where simplicity and a low number of changes are important.

The algorithm clearly demonstrates the concepts of:

Dividing a problem into subproblems
Loop invariants
Complexity analysis
Trade-offs between different performance metrics