Notes on Algorithms 2, Selection Sort

Last time I practiced the binary search algorithm and then implemented it on JavaScript. This time I learned about Selection Sort. A selection sort is a sorting algorithm that will take an array of numbers (or strings) and then sort them into ascending order. If I give an input of
[1, 5, 3, 4, 2] it will output [1, 2, 3, 4, 5].

In a nutshell I start with the first item of the list. Then I check the other items one by one and see if any of the other items are lower than my first item. If I find an item which is lower than the first item, I replace this one with the first item.

For the list of [3, 4, 2, 1] I take 3 as the first item. Then I check 4, 2 and 1 and see which one is lower than 3.

Finding the minimum index of a given array

I see 1 is the lowest so I will replace the positions of 3 and 1. I will have a new array of [1, 4, 2, 3].

Swap index 0 with index 3 to find a new array

Then on the second run, I pick 4 (which is in the 2nd position now) as the new start index. Once again I check the remaining values to see 2 is lower than 4. I replace the index of 4 with 2. Now I have an array of [1, 2, 4, 3].

On the next run I pick 4 as the new start index because 4 is now at the 3rd position of the array. I compare it against 3 to find 3 is obviously smaller than 4. I replace them to fine a new array of [1, 2, 3, 4]. Finally I don’t have anything to swap anymore and I am left with a sorted array.

The algorithm has a few sub algorithms:

Step 1: Find the minimum index

In this step, I will create a new function getMinimumIndex() which will take an array and the start index. It will then go from left to right and compare to see if any of the other items are smaller than the current. It will return the index of the lowest number.

/**
 * Get the minimum index of an array
 * @param array
 * @param startIndex
 * It will compare other items against the start index and output a minimum index
 * It will return an index
 * It will also mutate the array
 */
function getMinimumIndex(array, startIndex) {
  if (!array.length) return -1;

  // Set the min value to the start index
  let minValue = array[startIndex];
  let minIndex = startIndex;
  for (let i = startIndex + 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i];
      minIndex = i;
    }
  }
  return minIndex;
}

Step 2: Swap the first index with the second one

In this step I will create another function swap() which will take an array, the firstIndex and the secondIndex. The task of this function will be to swap the two values. Since the function will be inside our algorithm, it will mutate the original array.

/**
 * @param array
 * @param firstIndex
 * @param secondIndex
 * It will swap first index with second index
 * It will mutate the original array
 */
function swap(array, firstIndex, secondIndex) {
  if (!array.length) return -1;

  // Temporary hold the item
  let temp = array[firstIndex];
  // Swap the first one with the second one
  array[firstIndex] = array[secondIndex];
  array[secondIndex] = temp;
  return array;
}

Step 3: Put it all together in the main function

I will create a top level function selectionSort() and supply with an unsorted array. I will run the array with a for loop.

Inside the for loop I will have the getMinimumIndex(). I will supply the array and current index of the loop. This function will return a minimum index.

In the next step I will have the swap() function which will take the array, the current index as the first item and then the minimumIndex as the second item. The swap function will swap out the array. After all the operations I will have a sorted array.

/**
 * Selection sort function
 * @param array takes and array
 * Outputs the sorted array
 */
function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let minIndex = getMinimumIndex(array, i);
    swap(array, i, minIndex);
  }
  return array;
}

I wrote a couple of tests and found it correctly gets the minimum index, swaps the values and sorts the array. This algorithm takes O(n^2) time. I can do one optimization: I can put the variable minIndex outside of the for loop, so it wont create so many minIndex variables for n items of the array. See the code and tests in the repo.


Leave a Reply

Your email address will not be published. Required fields are marked *