Selection Sort — Understanding the Logic Behind the Algorithm

A very classic problem in the field of algorithms is the sorting problem — the goal is to arrange a set of data, usually in the form of a list, in ascending or descending order.

The Selection Sort algorithm is an excellent starting point. It’s great for understanding the concept of finding the smallest element and placing it in the correct position. The logic of comparing and swapping elements forms the foundation of all other sorting algorithms. Understanding Selection Sort is one of the best ways to truly grasp what sorting means, as it clearly illustrates the idea of finding the smallest element and putting it in its proper place.

Main Idea

The idea is to look at a list of data and always search for the smallest (or largest) element in the list. For this article, we’ll focus on sorting in ascending order.

Step-by-step example

Let’s follow the example from the list above. We have the array:

[7, 5, 1, 8, 3]

Step 1 — Find the smallest element

The smallest element is 1 — put it in the first position. Then swap 7 with 1, producing the new array:

[1, 5, 7, 8, 3]

Step 2 — Find the smallest in the remainder [5, 8, 3, 7]

The smallest element in the remaining list [5, 8, 3, 7] is 3 — put it in the next position. Then swap 5 with 3, producing the new array:

[1, 3, 7, 8, 5]

Step 3 — Find the smallest in the remainder [8, 5, 7]

The smallest element in [8, 5, 7] is 5 — put it in the next position. Then swap 8 with 5, producing the new array:

[1, 3, 5, 8, 7]

Step 4 — Find the smallest in the remainder [8, 7]

The smallest element in [8, 7] is 7 — put it in the next position. Then swap 8 with 7, producing the new array:

[1, 3, 5, 7, 8]

Step 5 — Only 8 remains, it’s already in place.

Done. Now the array is sorted:

[1, 3, 5, 7, 8]

On each loop iteration, the smallest element moves to the front — you literally “select” the smallest value, which is why it’s called Selection Sort.

Pseudocode

for each position i in the array:
    find the index of the smallest element from i to the end of the array
    swap the element at position i with the smallest element found

Line 1: for each position i in the array
- This means you’ll go through the array from left to right.
- i represents the position where the next smallest element will go.
- Example: if the array has 5 elements, i goes from 0 to 4.
Line 2: find the index of the smallest element from i to the end of the array
- Here, you only look at the part of the array that isn’t sorted yet.
- In other words, from the current index i to the last element.
- Find the smallest value in this sublist.
- Don’t touch the already sorted portion on the left.
- Example:
```
  Array: [7, 5, 1, 8, 3]
  i = 0  → subarray = [7, 5, 1, 8, 3]
  menor = 1
```
Line 3: swap the element at position i with the smallest element found
- After finding the smallest element, place it in the correct position (i).
- To do that, we usually perform a swap:
```
  temp = arr[i]
  arr[i] = arr[minIndex]
  arr[minIndex] = temp
```
- This ensures that the smallest number in the unsorted part moves to the front, gradually expanding the sorted section.

Overview of the logic:

i = 0 → find the smallest element in the entire array → swap it into position 0
i = 1 → find the smallest element in the remaining part → swap it into position 1
i = 2 → find the smallest element in the remaining part → swap it into position 2
Repeat this process until the end.

Each step ensures that one position is now permanently sorted — continuing this way until the entire array is ordered.

Big-O

The Selection Sort algorithm has a time complexity of O(n²). Let’s understand why:

Let’s recall the logic of Selection Sort:

For each position in the array:
- Find the smallest value in the remaining part of the array;
- Swap the smallest element with the element at the current position;
How many operations are performed?

Suppose the array has n elements:
- In the first iteration, you compare the first element with all other n−1 elements to find the smallest.
- In the second iteration, you compare the second element with the remaining n−2 elements.
- In the third iteration, you compare with n−3 elements, and so on…
- In the last iteration, only one element remains, so no comparisons are needed.
  
  Resumindo Visualmente:
```
  Iteration 1 → 4 comparisons
  Iteration 2 → 3 comparisons
  Iteration 3 → 2 comparisons
  Iteration 4 → 1 comparison
  Iteration 5 → 0 comparisons
  Total = 10 comparisons ≈ 5² / 2
```
Important Notes
- The dominant factor in execution time — that is, the time complexity — comes from the number of comparisons, which grows on the order of n².
- This doesn’t depend on whether the array is already sorted or not, so even in the best case, Selection Sort still runs in O(n²).

Selection Sort Algorithm — Step by Step

Let’s implement the Selection Sort algorithm in JavaScript, line by line, with clear comments so we can understand step by step how to solve this problem.

We want to sort an array from smallest to largest. The concept of Selection Sort is simple: “at each position, place the smallest element that hasn’t been placed yet.”

Step 1: Define the outer loop

  function selectionSort(arr) {
    const n = arr.length;

    /**
     * Each iteration of 'i' represents the position
     * where we will place the next smallest element.
     * We start at 0 because the first element is not
     * yet guaranteed to be in order.
     * We end at n-1 because the last element will be
     * in the correct place automatically after previous iterations.
     */
    for (let i = 0; i < n - 1; i++) {
      // code here
    }

    return arr;
  }

The outer loop is like saying: “Now I’ll fill this position with the smallest element from the unsorted part”.

Step 2: Initialize the index of the smallest element

  function selectionSort(arr) {
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
      /**
       * Assume the smallest element is at position 'i'.
       * Before searching, we assume the smallest element of the
       * unsorted sublist is at position 'i'.
       * This makes it easy to compare other array elements and
       * update when we find a smaller one.
       */
      let minIndex = i;
    }

    return arr;
  }

Step 3: Inner loop to find the smallest element

  function selectionSort(arr) {
    const n = arr.length;

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

      /**
       * Inner loop to search for the smallest element in
       * the remainder of the array.
       * The 'j' loop iterates over the unsorted portion of the array,
       * i.e., from i+1 to the end.
       * Each element arr[j] is compared with the current smallest (arr[minIndex]).
       * If we find a smaller value, we update minIndex.
       *
       * This ensures that at the end of the inner loop, minIndex will be
       * the index of the smallest remaining element.
       */
      for (let j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
          // Update the index of the smallest element found
          minIndex = j;
        }
      }
    }

    return arr;
  }

Step 4: Swap

  function selectionSort(arr) {
    const n = arr.length;

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

      for (let j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }

      /**
       * Swap the element at position 'i' with the smallest found
       *
       * Summary of the swap effect
       * - These three lines perform a swap between arr[i] and arr[minIndex].
       * - The swap is in-place (it does not create a new array), and is done in constant time O(1)
       *   and constant extra space O(1) (only the temporary variable).
       *
       * Concrete example (step by step)
       * arr = [7, 5, 1, 8, 3]
       * i = 0, minIndex = 2
       * temp = arr[0] -> temp = 7
       * arr[0] = arr[2] -> arr becomes [1, 5, 1, 8, 3]
       * arr[2] = temp   -> arr becomes [1, 5, 7, 8, 3]
       */
      if (minIndex !== i) {
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }

    return arr;
  }

Let’s go through it line by line and explain the reasoning behind each choice, using small examples to keep things clear.

if (minIndex !== i) {

  /**
   * if (minIndex !== i) { -> checks whether the index of the smallest element
   * found (minIndex) is different from the current position i.
   * If minIndex === i, it means the smallest element is already in the correct
   * position — there’s no need to swap anything.
   */
  if (minIndex !== i) {
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }

let temp = arr[i];

  /**
   * let temp -> temporarily stores the value currently at arr[i].
   *
   * If we did arr[i] = arr[minIndex] without saving arr[i] first,
   * we would lose the original value at arr[i] — it would be overwritten.
   * 'temp' preserves that value so we can later place it at position minIndex.
   */
  let temp = arr[i];

arr[i] = arr[minIndex];

  /**
   * puts at position i the value that was at minIndex — that is,
   * moves the smallest element found to position i.
   * Our goal is for position i to hold the smallest element
   * of the unsorted part. So we place arr[minIndex] in arr[i].
   * Example: if arr = [7, 5, 1, 8, 3], i = 0, minIndex = 2 (value 1),
   * then arr[0] becomes 1.
   */
  arr[i] = arr[minIndex];

arr[minIndex] = temp;

  /**
   * puts the value that was originally in arr[i] (stored in temp)
   * into position minIndex.
   * This completes the swap: now arr[minIndex] receives the value that was at i,
   * finishing the exchange without data loss.
   * Final result: the two elements have swapped places.
   */
  arr[minIndex] = temp;

Algoritmo completo em JavaScript

/**
 * Step 0:
 * Sort an array from smallest to largest!
 * At each position, place the smallest element that has
 * not yet been placed.
 */
function selectionSort(arr) {
  const n = arr.length;

  // Step 1:
  for (let i = 0; i < n - 1; i++) {

    // Step 2:
    let minIndex = i;

    // Step 3:
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Step 4:
    if (minIndex !== i) {
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  return arr;
}

const numbers = [7, 5, 1, 8, 3];
console.log('Sorted array:', selectionSort(numbers)); // [1, 3, 5, 7, 8]

Conclusion

The Selection Sort algorithm is an excellent starting point for understanding the fundamentals of sorting, as its logic is simple and easy to visualize. However, because it has a time complexity of O(n²), it becomes inefficient for large amounts of data. Therefore, in real-world applications, it is usually replaced by more efficient algorithms, such as Bubble Sort, Insertion Sort, or more advanced ones like Merge Sort, Quick Sort, and Heap Sort. Understanding Selection Sort, however, is essential for building a solid foundation before moving on to more sophisticated techniques.

Step by Step - Selection Sort

Main Idea

Step-by-step example

Pseudocode

Big-O

Selection Sort Algorithm — Step by Step

Algoritmo completo em JavaScript

Conclusion

Comments

More from this blog

Step by Step - Binary Search

Command Palette

Main Idea

Step-by-step example

Pseudocode

Big-O

Selection Sort Algorithm — Step by Step

Algoritmo completo em JavaScript

Conclusion

Comments

More from this blog