Chapter 16 of 65

Selection Sort

Imagine you have a handful of playing cards spread out on a table, and you want to arrange them from smallest to largest.

A very natural way to do it is:

  • Look at all the cards and pick the smallest. Put it first.

  • From the remaining cards, pick the smallest again. Put it second.

  • Keep going until no cards are left.

You are repeatedly selecting the minimum and placing it in the next position. That is Selection Sort.

In the previous chapter, Bubble Sort moved elements step by step with many small swaps. Selection Sort takes a different approach: it first finds the right element, then moves it into place with a single swap.


What is Selection Sort?

Selection Sort is a comparison-based sorting algorithm that divides the array into a sorted part and an unsorted part, and repeatedly selects the smallest element from the unsorted part and swaps it into the first position of the unsorted part.

At any moment the array looks like this:

[  sorted part  |  unsorted part  ]
  (final order)   (still to be processed)

At the start, the sorted part is empty. After every pass, it grows by one element, and the unsorted part shrinks by one.


How Selection Sort Works

Let's sort this array:

Index:  0   1   2   3   4
Value: 64  25  12  22  11

Pass 1 (i = 0)

Find the minimum in the whole array (indexes 0 to 4):

[64, 25, 12, 22, 11]
                  ↑
         minimum = 11 at index 4

Swap it with the element at index 0:

[11 | 25, 12, 22, 64]
  ↑
sorted

Pass 2 (i = 1)

Find the minimum in indexes 1 to 4:

[11 | 25, 12, 22, 64]
          ↑
   minimum = 12 at index 2

Swap with index 1:

[11, 12 | 25, 22, 64]

Pass 3 (i = 2)

Find the minimum in indexes 2 to 4:

[11, 12 | 25, 22, 64]
              ↑
       minimum = 22 at index 3

Swap with index 2:

[11, 12, 22 | 25, 64]

Pass 4 (i = 3)

Find the minimum in indexes 3 to 4:

[11, 12, 22 | 25, 64]
              ↑
   minimum = 25, already at index 3 → no swap needed
[11, 12, 22, 25 | 64]

Only one element, 64, is left. A single element is always in its correct place, so we are done:

[11, 12, 22, 25, 64]

After pass k, the k smallest elements are in their final positions at the front of the array.

Compare this with Bubble Sort, where the largest elements settle at the end first.


The Algorithm

1. For i = 0 to n - 2:
2.     minIndex = i
3.     For j = i + 1 to n - 1:
4.         If arr[j] < arr[minIndex]:
5.             minIndex = j
6.     Swap arr[i] and arr[minIndex]

The key idea is the variable minIndex. We do not swap while searching. We only remember where the smallest element is, and swap once at the end of the pass.

Notice that the inner part, "find the index of the minimum in a range", is just a linear search for the minimum, which you already know from the Linear Search chapter.


Selection Sort in Java

import java.util.Arrays;

class Main {

    static void selectionSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {

            // Assume the first unsorted element is the smallest
            int minIndex = i;

            // Find the actual smallest in arr[i..n-1]
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Put it at position i (one swap per pass)
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }

            System.out.println("Pass " + (i + 1) + ": min = " + arr[i]
                    + " -> " + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {

        int[] arr = {64, 25, 12, 22, 11};

        System.out.println("Original: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted:   " + Arrays.toString(arr));
    }
}

Output:

Original: [64, 25, 12, 22, 11]
Pass 1: min = 11 -> [11, 25, 12, 22, 64]
Pass 2: min = 12 -> [11, 12, 25, 22, 64]
Pass 3: min = 22 -> [11, 12, 22, 25, 64]
Pass 4: min = 25 -> [11, 12, 22, 25, 64]
Sorted:   [11, 12, 22, 25, 64]

The output follows our hand trace exactly. Notice that the outer loop runs only n - 1 times: once the first n - 1 elements are placed, the last one is automatically correct.

The if (minIndex != i) check is optional. Swapping an element with itself does no harm; the check just skips a useless swap.


Counting Comparisons and Swaps

Let's see how Selection Sort behaves on different kinds of input. The program below also includes two variations, a descending sort and a stability test, which we will discuss in the next sections.

import java.util.Arrays;

class Card {
    int value;
    String label;

    Card(int value, String label) {
        this.value = value;
        this.label = label;
    }

    @Override
    public String toString() {
        return value + label;
    }
}

class Main {

    static int comparisons;
    static int swaps;

    static void selectionSort(int[] arr) {
        comparisons = 0;
        swaps = 0;
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                comparisons++;
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
                swaps++;
            }
        }
    }

    // Selection sort on cards, comparing only the value
    static void selectionSortCards(Card[] cards) {
        int n = cards.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (cards[j].value < cards[minIndex].value) {
                    minIndex = j;
                }
            }
            Card temp = cards[i];
            cards[i] = cards[minIndex];
            cards[minIndex] = temp;
        }
    }

    // Descending order: select the maximum instead
    static void selectionSortDescending(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }

    static void report(String label, int[] input) {
        int[] copy = input.clone();
        selectionSort(copy);
        System.out.println(label + " " + Arrays.toString(input)
                + " -> comparisons = " + comparisons + ", swaps = " + swaps);
    }

    public static void main(String[] args) {

        report("Sorted  ", new int[]{1, 2, 3, 4, 5, 6});
        report("Reversed", new int[]{6, 5, 4, 3, 2, 1});
        report("Random  ", new int[]{3, 6, 1, 5, 2, 4});

        int[] marks = {72, 95, 58, 88, 64};
        selectionSortDescending(marks);
        System.out.println("Descending: " + Arrays.toString(marks));

        Card[] cards = {
            new Card(5, "a"), new Card(3, ""), new Card(5, "b"), new Card(1, "")
        };
        System.out.println("Before: " + Arrays.toString(cards));
        selectionSortCards(cards);
        System.out.println("After:  " + Arrays.toString(cards));
    }
}

Output:

Sorted   [1, 2, 3, 4, 5, 6] -> comparisons = 15, swaps = 0
Reversed [6, 5, 4, 3, 2, 1] -> comparisons = 15, swaps = 3
Random   [3, 6, 1, 5, 2, 4] -> comparisons = 15, swaps = 4
Descending: [95, 88, 72, 64, 58]
Before: [5a, 3, 5b, 1]
After:  [1, 3, 5b, 5a]

Look carefully at the first three lines:

  • The number of comparisons is always 15, whether the array is sorted, reversed or random. Selection Sort cannot tell that an array is already sorted; it still searches for the minimum in every pass.

  • The number of swaps is very small: never more than n - 1. For the reversed array, only 3 swaps were needed (6↔1, 5↔2, 4↔3), while Bubble Sort needed 15 for the same input.


Time and Space Complexity

The inner loop scans the whole unsorted part in every pass:

Pass 1 → n - 1 comparisons
Pass 2 → n - 2 comparisons
...
Pass n-1 → 1 comparison

Total = n(n - 1) / 2

For n = 6: 6 × 5 / 2 = 15, exactly what the program printed for every input.

This number does not depend on the order of the input. So:

Case

Comparisons

Swaps

Time

Best (already sorted)

n(n − 1)/2

0

O(n²)

Average

n(n − 1)/2

at most n − 1

O(n²)

Worst

n(n − 1)/2

at most n − 1

O(n²)

Using the notation from the Big O, Big Ω & Big Θ chapter, Selection Sort is Θ(n²) in every case.

Space complexity is O(1): only i, j, minIndex and temp are used. Selection Sort is in-place.


Is Selection Sort Stable?

No. The standard Selection Sort is not stable.

The problem is the long-distance swap. When the minimum is swapped into position i, the element that was at position i gets thrown far away, possibly jumping over an equal element.

Look at the card example from our program. We have two cards with value 5, labelled a and b so we can tell them apart:

Before: [5a, 3, 5b, 1]      ← 5a comes before 5b

Pass 1: the minimum is 1 at index 3. Swap it with index 0:

[1, 3, 5b, 5a]              ← 5a jumped over 5b!

Pass 2 and Pass 3 make no further changes, because 3 is already the minimum of its range, and 5a is not strictly smaller than 5b.

After:  [1, 3, 5b, 5a]      ← order of equal elements changed

The values are correctly sorted, but the two 5s have swapped their relative order. That is exactly what "unstable" means.

A stable version is possible: instead of swapping, take the minimum out and shift the elements in between one step to the right. But shifting costs many more writes, which removes Selection Sort's main advantage.


Variations

Descending Order

Select the maximum instead of the minimum (change < to >), as shown in selectionSortDescending above.

Selecting the Maximum to the End

Another equally valid version finds the maximum of the unsorted part and swaps it to the end. The sorted part then grows from the right, similar to Bubble Sort, but still with only one swap per pass.

Finding the k Smallest Elements

If you only need the k smallest elements in order, you can stop Selection Sort after k passes. That costs O(n·k) instead of O(n²), which is useful when k is very small.


Selection Sort vs Bubble Sort

Feature

Bubble Sort

Selection Sort

Main idea

Swap adjacent elements that are out of order

Find the minimum, then swap it into place

After pass k

k largest at the end

k smallest at the front

Best case

O(n) (with swapped flag)

O(n²)

Worst case

O(n²)

O(n²)

Number of swaps

Up to n(n − 1)/2

At most n − 1

Stable?

Yes

No

Adaptive?

Yes (with flag)

No

In-place?

Yes

Yes

In short: Bubble Sort is better when the data might already be sorted; Selection Sort is better when swaps (writes) are expensive.


Common Mistakes

1. Swapping Inside the Inner Loop

// Not Selection Sort
for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[i]) {
        swap(arr, i, j);     // swaps every time a smaller value is seen
    }
}

This still sorts the array, but it can make many swaps per pass, which throws away Selection Sort's key benefit of one swap per pass. Remember: find first, swap once.

2. Wrong Starting Value for minIndex

minIndex must start at i (the first unsorted position), not at 0. Starting at 0 would keep picking elements from the already sorted part.

3. Inner Loop Starting at 0

The inner loop must start at i + 1. Searching from 0 looks into the sorted part and breaks the algorithm.

4. Comparing Values Instead of Using the Index

Storing only the minimum value is not enough; you need its index to perform the swap.


When Should You Use Selection Sort?

Selection Sort is useful when:

  • The array is small

  • Writing to memory is much more expensive than reading (for example, some flash memory), because it makes at most n - 1 swaps

  • You need the code to be very simple and predictable, since it always does the same amount of work

Avoid it for large datasets, and when you need a stable sort, or when the input is often already sorted.


Interview Tips and Practice

  • Be ready to trace Selection Sort by hand and show the sorted/unsorted boundary after each pass.

  • Remember the two "always" facts: it always makes n(n − 1)/2 comparisons, and it makes at most n − 1 swaps.

  • Be able to explain with an example why it is not stable.

  • A common question: "Which simple sort makes the fewest swaps?" Answer: Selection Sort.

Practice:

  • Sort an array of Strings alphabetically using Selection Sort.

  • Sort an array in descending order by moving the maximum to the front.

  • Find the 3 smallest elements of an array using only 3 passes of Selection Sort.

  • Write a stable version of Selection Sort that shifts elements instead of swapping.

  • Sort a list of students by marks using Selection Sort, and check whether students with equal marks keep their order.


The Main Idea

Selection Sort repeatedly selects the smallest element from the unsorted part and swaps it into the next position of the sorted part.

For i = 0 to n - 2:
        ↓
Find minimum in arr[i..n-1]
        ↓
Swap it with arr[i]
        ↓
Sorted part grows by one

The facts to remember:

Time (all cases) → O(n²)
Comparisons      → always n(n - 1)/2
Swaps            → at most n - 1
Space            → O(1)
Stable           → No
Adaptive         → No

Selection Sort is simple and makes very few swaps, but it always takes O(n²) time and is not stable. Next, we will look at Insertion Sort, a simple sort that is stable and becomes very fast on nearly sorted data.