Sorting Algorithms: Part 2

This is a continuation of the sorting algorithms series. This article will cover selection sort. .

Problem

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[0]. Then find the second smallest element of A, and exchange it with A[1]. Continue in this manner for the first n−1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. Why does this algorithm need to run for only the first n−1 elements, rather than for all n elements?

Pseudocode

1. Loop through the first n - 1 elements of the input array (using an iterator i)

2. Declare a variable smallestIndex and initialize it to i.

   • Create an inner loop starting at the i + 1 th element till the end of the array.

     • Compare the number at arr[j] with the number at smallestIndex. If currNumber is smaller than the number at the smallestIndex then reassign the smallestIndex’s value to j. This means we have found a smaller number.

   • At the end of the inner loop, swap currentNum with the number at smallestIndex.

3. Return the input array

Code in Javascript

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let smallestIndex = i;
    for (let j = i + 1; j < arr.length; j++){
      if (arr[j] < arr[smallestIndex]) {
        smallestIndex = j;
      }
    }
    //use array destructuring to swap currentElement with smallestElement
    [arr[smallestIndex], arr[i]] = [arr[i], arr[smallestIndex]];
  }
  return arr;
}

Time Complexity:

• Time Complexity for the algorithm is O(N²).

• For every element - we loop through the rest of the elements in front of it, looking for the smallest element. For example we need to loop over the next n - 1 numbers for the first element in the array, n - 2 for the second number, and so on result in

$$(n - 1) + (n -2) + (n - 3) + ... + 1 = n(n - 1)/2 = (n^2 - n)/2$$

Space Complexity:

• We dont use any significant extra space for this algorithm.

Selection sort vs Insertion Sort

• Selection sort is preferable to insertion sort if swaps need to be minimized because it has fewer swaps. Selection sort has up to n - 1 swaps, whereas insertion sort has at most (n^2 - n)/2 swaps.

• Selection sort is unstable, meaning it doesn't preserve the relative order of elements with the same value. If stability is essential, go with insertion sort.

• Selection sort always has O(N²) time complexity, even when the array is already sorted. The algorithm loops and compares all elements even when sorted. Insertion sort is more efficient if your input array is almost sorted.

• Both algorithms are more efficient for smaller arrays and perform poorly for larger data sets.

And there you have it! One more sorting algorithm in the bag!

Happy coding!