Selection Sort

Say you have a row of exam papers and you want them sorted by marks, lowest first. Here is one simple way. You look at the whole pile, pick the paper with the lowest marks, and put it at the very front. Then you look at what is left. You pick the smallest from that and put it next. You keep going till nothing is left. That is exactly what selection sort does. It picks the smallest item from the unsorted part and moves it to the front, again and again.

🤔 What Selection Sort Actually Does

The idea is that selection sort splits your array into two parts in your head.

• A sorted part on the left. This starts empty.
• An unsorted part on the right. This starts as the whole array.

In each round you do one job. You scan the unsorted part. You find the smallest value. Then you swap it to the front of the unsorted part. Now that value is in its final spot. So the sorted part grows by one and the unsorted part shrinks by one.

You repeat this for every position. After the last round the whole array is sorted.

🔍 A Small Trace

Let us sort [29, 10, 14, 37, 13] from small to large. Watch how the smallest value moves to the front each round.

We start with the full array unsorted. The smallest value is 10, so we swap it with the front.

Start:    [29, 10, 14, 37, 13]
Round 1:  pick 10 -> swap with 29 -> [10, 29, 14, 37, 13]

Now 10 is locked. We look at the rest [29, 14, 37, 13]. The smallest is 13, so we swap it to the front of that part.

Round 2:  pick 13 -> swap with 29 -> [10, 13, 14, 37, 29]

Now 10, 13 are locked. The smallest of [14, 37, 29] is 14. It is already at the front, so the swap does nothing.

Round 3:  pick 14 -> already in place -> [10, 13, 14, 37, 29]

Now look at [37, 29]. The smallest is 29, so we swap it.

Round 4:  pick 29 -> swap with 37 -> [10, 13, 14, 29, 37]

Only one value is left, so it is already sorted. We are done.

Final:    [10, 13, 14, 29, 37]

See the pattern? For an array of n items you do n - 1 rounds. The last item falls into place on its own.

📝 Steps to Sort

Here is the plain recipe before we write any code.

1. Start at the first position. Call it i.
2. Assume the item at i is the smallest. Remember its index as minIndex.
3. Look at every item from i + 1 to the end. If you find a value smaller than the one at minIndex, update minIndex to that position.
4. After the scan, swap the item at i with the item at minIndex. The smallest value of the unsorted part is now in place.
5. Move i forward by one and repeat until i reaches the second-last position.

The inner scan is the part that finds the smallest. The outer loop just decides which position we are filling next.

💻 Selection Sort in Code

Now let us turn that recipe into a real program. Each version writes a selectionSort function, calls it on the same array, and prints the result.

#include <stdio.h>

// Sort the array from small to large
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;              // assume current spot holds the smallest
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;          // found a smaller value
            }
        }
        // swap the smallest found into position i
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = 5;
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

10 13 14 29 37

#include <iostream>
using namespace std;

// Sort the array from small to large
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;              // assume current spot holds the smallest
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;          // found a smaller value
            }
        }
        swap(arr[i], arr[minIndex]);   // put the smallest into position i
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = 5;
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

10 13 14 29 37

public class SelectionSort {

    // Sort the array from small to large
    static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;              // assume current spot holds the smallest
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;          // found a smaller value
                }
            }
            // swap the smallest found into position i
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};
        selectionSort(arr);
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

10 13 14 29 37

# Sort the list from small to large
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i                  # assume current spot holds the smallest
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j          # found a smaller value
        # swap the smallest found into position i
        arr[i], arr[min_index] = arr[min_index], arr[i]


numbers = [29, 10, 14, 37, 13]
selection_sort(numbers)
print(numbers)

[10, 13, 14, 29, 37]

// Sort the array from small to large
function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;                  // assume current spot holds the smallest
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;                  // found a smaller value
      }
    }
    // swap the smallest found into position i
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
}

const numbers = [29, 10, 14, 37, 13];
selectionSort(numbers);
console.log(numbers.join(" "));

10 13 14 29 37

⏱️ How Fast Is It?

Let us count the work. The outer loop runs about n times. For each of those, the inner scan looks at the rest of the array. So you compare items again and again. The total comes to about n * n / 2 comparisons. We drop the constants and call that O(n^2) time.

Here is the part that surprises people. Selection sort does the same number of comparisons no matter what. Even if the array is already sorted, it still scans the whole unsorted part every round to be sure it found the smallest. So the best case is also O(n^2). It cannot finish early.

The good news is space. It sorts inside the same array. It only uses a couple of extra variables like minIndex and a temp value for the swap. That is O(1) extra space.

Here is the full picture in one table.

One small plus point. Selection sort does at most n - 1 swaps total, one per round. So when writing to memory is very costly and reading is cheap, it can be a fair pick even with its slow compare count.

⚠️ Common Mistakes

A few slip-ups show up again and again. Watch for these.

• Running the outer loop all the way to n instead of n - 1. The last item is already in place, so the extra round just wastes time.
• Starting the inner loop at i instead of i + 1. Comparing an item with itself does nothing useful.
• Swapping inside the inner loop instead of once after it. It still works but does far more swaps than needed.
• Forgetting to reset minIndex to i at the start of each round. If you carry over the old value, the result is wrong.

🧩 What You’ve Learned

• ✅ Selection sort splits the array into a sorted left part and an unsorted right part.
• ✅ Each round it picks the smallest value from the unsorted part and swaps it to the front.
• ✅ For n items you run n - 1 rounds, with one swap per round.
• ✅ Time is O(n^2) in every case, even when the array is already sorted.
• ✅ It sorts in place with O(1) extra space, but it is not stable.

🚀 What’s Next?

• Bubble Sort
• Insertion Sort