How Selection Sort Works: Step-by-Step Explanation

Sorting data is a fundamental task in computer science, and selection sort is one of the easiest ways to do it. This article will guide you through the selection sort algorithm with clear, easy-to-understand explanations. Whether you’re a student, a new programmer, or just curious, you’ll see how selection sort works and why it’s a useful starting point for learning about sorting. Let’s get started!

Note: This article focusses on selection sort algorithm to sort an array in ascending order. If you wish to sort in descending order, all the steps remain same, but instead of finding the next minimum element, you need to look for the next maximum element.

What is Selection Sort

Selection sort is a simple sorting algorithm that works by repeatedly finding the smallest element from the unsorted part of a list and moving it to the beginning. The algorithm divides the list into two parts:

  1. The sorted portion, which starts empty and grows from left to right as we find the smallest elements.
  2. The unsorted portion, which contains the elements that haven’t been sorted yet.

The core idea is to build a sorted list one element at a time by repeatedly selecting the smallest remaining element and moving it to its correct position.

For a more in-depth introduction, you might find this article helpful: Introduction to Selection Sort Algorithm.

Algorithm for Selection Sort

Here’s how the selection sort algorithm works:

  1. Find the smallest: Look through the unsorted part of the list to find the smallest element.
  2. Swap: Exchange the smallest element with the first element of the unsorted part. This puts the smallest element in its correct sorted position.
  3. Move the boundary: Imagine a line between the sorted and unsorted parts. Move this line one element to the right. This means the sorted part has grown by one element, and the unsorted part has shrunk by one.
  4. Repeat: Keep doing this until the entire list is sorted.

Step-by-Step Walkthrough of Selection Sort Algorithm

Let’s walk through an example to see selection sort in action. Suppose we have the following unsorted list of numbers:

[64, 25, 12, 22, 11]

Here’s how selection sort would sort this list:

  1. First Pass:
    • Unsorted portion: [64, 25, 12, 22, 11]
    • Find the smallest element in the unsorted portion: 11 is the smallest.
    • Swap the smallest element in the unsorted portion (11) with the first element in the unsorted portion (64): [11, 25, 12, 22, 64]
    • Sorted portion: [11]
    • Unsorted portion: [25, 12, 22, 64]

Below is the visual animation of this step:

  1. Second Pass:
    • Unsorted portion: [25, 12, 22, 64]
    • Find the smallest element in the unsorted portion: 12 is the smallest.
    • Swap the smallest element in the unsorted portion (12) with the first element in the unsorted portion (25): [11, 12, 25, 22, 64]
    • Sorted portion: [11, 12]
    • Unsorted portion: [25, 22, 64]

Below is the visual animation of this step:

  1. Third Pass:
    • Unsorted portion: [25, 22, 64]
    • Find the smallest element in the unsorted portion: 22 is the smallest.
    • Swap the smallest element in the unsorted portion (22) with the first element in the unsorted portion (25): [11, 12, 22, 25, 64]
    • Sorted portion: [11, 12, 22]
    • Unsorted portion: [25, 64]

Below is the visual animation of this step:

  1. Fourth Pass:
    • Unsorted portion: [25, 64]
    • Find the smallest element in the unsorted portion: 25 is the smallest.
    • Swap the smallest element in the unsorted portion (25) with the first element in the unsorted portion (25): [11, 12, 22, 25, 64] (no change as it’s already in place)
    • Sorted portion: [11, 12, 22, 25]
    • Unsorted portion: [64]

Below is the visual animation of this step:

  1. Fifth Pass:
    • Unsorted portion: [64]
    • Find the smallest element in the unsorted portion: 64 is the smallest.
    • Swap the smallest element in the unsorted portion (64) with the first element in the unsorted portion (64): [11, 12, 22, 25, 64] (no change as it’s already in place)
    • Sorted portion: [11, 12, 22, 25, 64]
    • Unsorted portion: Empty

After these steps, the list is fully sorted: [11, 12, 22, 25, 64].

Key Concepts and Operations

Let’s make sure we really understand selection sort by looking at the key ideas and actions involved. Think of these concepts as the basic building blocks that make selection sort work.

Maintaining Two Portions

  • The array is divided into two logical parts:
    • Sorted portion (on the left highlighted in green): These elements are already in the correct order.
    • Unsorted portion (on the right): These elements still need to be sorted.
  • At the start, the sorted portion is empty.
  • As the sorting goes on, the boundary between the sorted and unsorted portions moves to the right.
  • With each step, the sorted portion grows, and the unsorted portion gets smaller.

Finding the Minimum

  • Finding the minimum requires us to check each element in the unsorted portion to see if it’s the smallest.
  • We keep track of the index (position) of this smallest element.

Swapping

  • We swap the smallest element with the element at the beginning of the unsorted portion.
  • This moves the smallest element to its correct spot in the sorted portion.
  • After the swap, the first element of the unsorted portion is now part of the sorted portion.

What’s Next?

Now that you understand how selection sort works, you might want to: