Selection Sort

Mark as Completed

Lesson

Write a JavaScript function that sorts an array using the selection sort algorithm. Explain the selection sort algorithm and its time complexity.

Example usage:

const arr = [4, 1, 3, 2, 5];
console.log(selectionSort(arr)); // [1, 2, 3, 4, 5]

Walkthrough

The selection sort algorithm is a simple sorting algorithm that iterates through the array and selects the minimum element in each iteration, then places it at the beginning of the array. The algorithm then moves on to the next element and finds the minimum in the remaining unsorted portion of the array, and repeats the process until the entire array is sorted.

To implement the selection sort algorithm in JavaScript, we can create a function called selectionSort
that takes an array as its argument. Inside the function, we first declare a variable to store the length of the array. We then iterate over the array using a for loop, selecting the minimum element in each iteration using another for loop that starts at the current index plus one and continues to the end of the array. If the minimum element is found, we swap it with the current element. We repeat this process until the entire array is sorted.Here is the code for the selectionSort
function:

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

  for (let i = 0; i < len; i++) {
    let min = i;

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

    if (min !== i) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }

  return arr;
}

Big O Complexity Analysis:

The time complexity of the selection sort algorithm is quadratic O(n^2) because of the nested for loops. In the worst-case scenario, the algorithm has to go through the entire array n times, resulting in n^2 operations. The space complexity of the algorithm is constant O(1) because we are not using any additional data structures to sort the array. The array is sorted in place.

In terms of time complexity, selection sort is less efficient than many other sorting algorithms, such as quicksort, mergesort, and heapsort, which have a time complexity of O(n log n). However, it is simple to understand and easy to implement, making it a good choice for small arrays.

Overall, selection sort is a simple but inefficient sorting algorithm. While it is easy to implement, there are many other more efficient sorting algorithms available for larger arrays.

Previous Lesson Next Lesson