Sorting

Selection Sort

A simple sorting algorithm that repeatedly finds the minimum value in the unsorted region and places it into its final position.

Selection sort works like organizing books or cards: for each position in the array, scan the remaining unsorted part, find the smallest value, and move it into the next sorted spot.

It is easy to learn because each pass has one clear goal: lock one more element into its final place. That makes the algorithm predictable and beginner-friendly.

Watch Visualization View Pseudocode

Quick Facts

Main Idea

Divide the array into a sorted left side and an unsorted right side.

Key Operation

Scan the unsorted region to find the smallest element, then swap it into place.

Predictable Behavior

Each pass places exactly one element into its final sorted position.

Swap Count

Selection sort usually makes fewer swaps than some other simple quadratic sorts.

Key Idea

Selection sort does not build order by shifting values into place. Instead, it repeatedly searches for the minimum in the remaining unsorted portion.

Once the minimum is found, it is swapped into the next position of the sorted region. Then the boundary moves forward, and the process repeats.

Visualization

This visualization emphasizes the scan for the minimum, the currently selected minimum index, and the final swap that locks the next element into the sorted region.

How It Works

Set the Boundary

Position i marks where the next smallest value should go.

Scan the Unsorted Part

Search from i to the end of the array to find the smallest value.

Remember the Minimum Index

Track the position of the current minimum while scanning.

Swap into Place

After the scan is complete, swap the minimum element into position i.

Why It Matters

Easy to Understand

Each pass has one clear purpose, which makes the algorithm easy to explain and trace.

Good for Teaching

Selection sort helps learners understand sorted and unsorted regions, scanning logic, and swapping.

Small Code Footprint

The algorithm is compact and often used when simplicity matters more than speed.

Useful Comparison Point

It provides a strong contrast with insertion sort, which shifts values rather than selecting a minimum.

Pseudocode

This pseudocode shows the full selection sort process:

for i from 0 to n - 2:
    min_index = i

    for j from i + 1 to n - 1:
        if A[j] < A[min_index]:
            min_index = j

    if min_index != i:
        swap A[i], A[min_index]

The important detail is that the algorithm finishes the full scan before doing the swap.

Performance

Time Complexity

Best case: O(n²)
Average case: O(n²)
Worst case: O(n²)

Space & Stability

Extra space: O(1)
In-place: Yes
Stable: No, in the usual swap-based form

Even if the array is nearly sorted, selection sort still performs the same overall number of comparisons.

Common Mistakes

Swapping Too Early

You should not swap every time you see a smaller value. Finish the scan first, then swap once.

Forgetting to Reset min_index

At the start of each pass, the minimum index must be reset to the current boundary i.

Unnecessary Swaps

If the minimum is already at position i, there is no need to swap.

Assuming It Is Stable

Because it uses swaps, selection sort can change the relative order of equal elements.

Outcome

After this lesson, learners should be able to explain how selection sort grows a sorted region, describe the scan-for-minimum process, read the basic pseudocode, and understand why the algorithm is simple but still quadratic in time.

Back to Home