Selection Sort

Definition

Selection sort is a comparison-based sorting algorithm that divides the list into two parts: a sorted part and an unsorted part. In each pass, it selects the minimum element from the unsorted part and swaps it with the first element of that unsorted section, thereby expanding the sorted part by one element.

Main Content

1. How Selection Sort Works

The array is treated as two sections:
the sorted portion at the beginning
the unsorted portion that contains the remaining elements
In each pass, the algorithm scans the unsorted portion to find the smallest element and places it in the correct position at the start of that unsorted section.

For example, consider the list:

[64, 25, 12, 22, 11]

Pass 1:
Find the smallest element in the entire list: 11
Swap it with the first element 64:

[11, 25, 12, 22, 64]

Pass 2:
Now the first element is fixed. Find the smallest in [25, 12, 22, 64], which is 12
Swap it with 25:

[11, 12, 25, 22, 64]

This process continues until the array becomes fully sorted.

The key idea is selection, not repeated insertion:
it selects the minimum element from the unsorted section
then moves it to its final position

2. Characteristics of Selection Sort

In-place sorting

Selection sort sorts the array without needing extra arrays or significant additional memory. Only a few temporary variables are required for swapping.

Comparison-based

The algorithm depends on comparing elements with each other to decide which one is smaller or larger.

Unstable by default

A sorting algorithm is called stable if equal elements keep their relative order after sorting. Selection sort is usually not stable because swapping can change the order of equal elements.

Deterministic behavior

For a given input, selection sort always performs the same sequence of operations. Its structure does not depend on the initial order of the elements in a major way.

Simple but inefficient for large inputs

Even if the list is already sorted, selection sort still scans the remaining elements to find the minimum, so it does not take advantage of pre-sorted data.

3. Time and Space Complexity

Time complexity

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

This happens because the algorithm always searches the remaining unsorted section for the minimum element, requiring a large number of comparisons.

For an array of size n:

first pass compares n - 1 elements
second pass compares n - 2 elements
third pass compares n - 3 elements
and so on

Total comparisons:

(n - 1) + (n - 2) + ... + 1 = n(n - 1)/2

This is why selection sort is quadratic in time.

Space complexity

O(1)
It uses constant extra memory, which makes it memory-efficient.

Number of swaps

At most n - 1 swaps are needed, which is fewer than some other simple sorting algorithms such as bubble sort.

Working / Process

1. Initialize the first position as the starting point of the unsorted section.

Assume the first element is the minimum, then scan the rest of the list to verify whether a smaller element exists.

2. Find the minimum element in the unsorted part.

Compare every element in the unsorted section and keep track of the smallest value and its index.

3. Swap the minimum element with the first unsorted element and repeat.

Move the sorted boundary one step forward and continue until the entire array is sorted.

For a clearer view, consider the array:

[29, 10, 14, 37, 13]

Pass 1: smallest = 10
[10, 29, 14, 37, 13]

Pass 2: smallest in [29, 14, 37, 13] = 13
[10, 13, 14, 37, 29]

Pass 3: smallest in [14, 37, 29] = 14
No change:

[10, 13, 14, 37, 29]

Pass 4: smallest in [37, 29] = 29
[10, 13, 14, 29, 37]

The list is now sorted.

A simple visual idea of the process:

[sorted | unsorted]

After each pass, the sorted region grows:

[10 | 29, 14, 37, 13]
[10, 13 | 14, 37, 29]
[10, 13, 14 | 37, 29]
[10, 13, 14, 29 | 37]

This shows how selection sort gradually fixes one element at a time.

Advantages / Applications

Easy to understand and implement

Selection sort is one of the most beginner-friendly sorting algorithms because its logic is direct and easy to trace.

Requires very little extra memory

Since it sorts in-place, it is useful in memory-constrained situations where using additional arrays is undesirable.

Useful for small datasets or educational purposes

For small lists, the simplicity of selection sort can be more important than performance. It is also widely used in teaching algorithm basics, such as comparisons, swaps, and complexity analysis.

Summary

Selection sort repeatedly finds the smallest element in the unsorted part and places it in the correct position.
It is simple, in-place, and easy to understand, but inefficient for large lists because it uses many comparisons.
It is a basic comparison-based sorting method commonly studied in algorithm fundamentals.
Important terms to remember: sorted section, unsorted section, minimum element, comparison-based, in-place, unstable