Mastering Selection Sort Algorithm like a PRO

As we've been talking about different sorting algorithms, today we'll be learning about the selection sort algorithm. A sorting algorithm that allows for the possible minimum amount of swaps in a memory-constrained environment.

Table of Contents

1. Introduction
2. What is Selection Sort Algorithm?
3. How does selection sort work?
   • Time Complexity
   • Space Complexity
4. Implementation in JavaScript
5. Solving LeetCode Problems
6. Conclusion

Introduction

Selection sort is a simple yet effective sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the beginning (or end) of the sorted portion. This process is repeated until the entire list is sorted. In this article, we will delve into the details of the selection sort algorithm, its implementation in JavaScript, and its applications in solving real-world problems.

What is Selection Sort Algorithm?

Selection Sort algorithm is an in-place comparison sorting algorithm. It divides the input list into two parts:

1. The sorted portion at the left end
2. The unsorted portion at the right end

The algorithm repeatedly selects the smallest element from the unsorted portion and swaps it with the leftmost unsorted element, moving the boundary between the sorted and unsorted portions one element to the right.

How does selection sort work?

Let's walk through an example using the array [64, 25, 12, 22, 11]:

1. Initial array: [64, 25, 12, 22, 11]

• Sorted portion: []
• Unsorted portion: [64, 25, 12, 22, 11]

1. First pass:

• Find minimum in unsorted portion: 11
• Swap 11 with first unsorted element (64)
• Result: [11, 25, 12, 22, 64]
• Sorted portion: [11]
• Unsorted portion: [25, 12, 22, 64]

1. Second pass:

• Find minimum in unsorted portion: 12
• Swap 12 with first unsorted element (25)
• Result: [11, 12, 25, 22, 64]
• Sorted portion: [11, 12]
• Unsorted portion: [25, 22, 64]

1. Third pass:

• Find minimum in unsorted portion: 22
• Swap 22 with first unsorted element (25)
• Result: [11, 12, 22, 25, 64]
• Sorted portion: [11, 12, 22]
• Unsorted portion: [25, 64]

1. Fourth pass:

• Find minimum in unsorted portion: 25
• 25 is already in the correct position
• Result: [11, 12, 22, 25, 64]
• Sorted portion: [11, 12, 22, 25]
• Unsorted portion: [64]

1. Final pass:
   • Only one element left, it's automatically in the correct position
   • Final result: [11, 12, 22, 25, 64]

The array is now fully sorted.

Time Complexity

Selection Sort has a time complexity of O(n^2) in all cases (best, average, and worst), where n is the number of elements in the array. This is because:

• The outer loop runs n-1 times
• For each iteration of the outer loop, the inner loop runs n-i-1 times (where i is the current iteration of the outer loop)

This results in approximately (n^2)/2 comparisons and n swaps, which simplifies to O(n^2).

Due to this quadratic time complexity, Selection Sort is not efficient for large datasets. However, its simplicity and the fact that it makes the minimum possible number of swaps can make it useful in certain situations, especially when auxiliary memory is limited.

Space Complexity

Selection Sort has a space complexity of O(1) because it sorts the array in-place. It only requires a constant amount of additional memory space regardless of the input size. This makes it memory-efficient, which can be advantageous in memory-constrained environments.

Implementation in JavaScript

Here's a JavaScript implementation of Selection Sort Algorithm:

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

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

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

Let's break down the code:

1. We define a function selectionSort that takes an array as input.
2. We iterate through the array with the outer loop (i), which represents the boundary between the sorted and unsorted portions.
3. For each iteration, we assume the first unsorted element is the minimum and store its index.
4. We then use an inner loop (j) to find the actual minimum element in the unsorted portion.
5. If we find a smaller element, we update minIndex.
6. After finding the minimum, we swap it with the first unsorted element if necessary.
7. We repeat this process until the entire array is sorted.

Solving LeetCode Problems

Let'solve one leetcode algorithm problem using selection sort algorithm. Shall we?

Problem: Sort An Array [Medium]

Problem: Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Approach:: To solve this problem, we can directly apply the Selection Sort algorithm. This involves iterating through the array, finding the smallest element in the unsorted portion, and swapping it with the first unsorted element. We repeat this process until the entire array is sorted.

Solution:

// This function sorts an array of integers in ascending order using the Selection Sort algorithm.
const sortArray = function (nums) {
  // Get the length of the input array.
  const n = nums.length;

  // Iterate through the array, starting from the first element.
  for (let i = 0; i < n - 1; i++) {
    // Initialize the index of the minimum element to the current element.
    let minIndex = i;

    // Find the minimum element in the unsorted portion of the array.
    for (let j = i + 1; j < n; j++) {
      if (nums[j] < nums[minIndex]) {
        // Update the minimum index if a smaller element is found.
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element if necessary.
    if (minIndex !== i) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }

  // Return the sorted array.
  return nums;
};

This solution directly applies the Selection Sort algorithm we implemented earlier. While it correctly solves the problem, it's worth noting that this solution may exceed the time limit for large inputs on LeetCode due to the O(n^2) time complexity of Selection Sort. The image below shows that the solution is correct but not efficient.

Conclusion

In conclusion, Selection Sort is a simple and intuitive sorting algorithm that serves as an excellent introduction to the world of sorting techniques. Its simplicity makes it easy to understand and implement, making it a valuable learning tool for beginners. However, due to its quadratic time complexity O(n^2), it is not efficient for large datasets. For larger datasets or performance-critical applications, more efficient algorithms like QuickSort, MergeSort, or built-in sorting functions are preferred.

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

Emmanuel Ayinde Follow

Software Engineer | Technical Writer | Backend, Web & Mobile Developer 💻 | Passionate about crafting efficient and scalable software solutions

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding 👨‍💻🚀