Objective

Given an array of numbers, sort it using the selection sort algorithm.

Difficulty

Easy

Description

Sorting is one of the most useful aspects of studying programming and computer algorithms. At its core, it's just to rearrange the existing elements of an array such that they line up in ascending order.

That is, the smallest element comes first, then the second smallest element, then the third smallest element, and so on and so forth.

Now there are various kinds of sorting algorithms. Each attacks the problem of sorting in a different way. One particularly simple and intuitive sorting algorithms is selection sort.

It proceeds as follows:

  1. The minimum is found in the entire array, and swapped with the first element.
  2. Next, the minimum is found in the entire array starting at index 1, and swapped with the second element.
  3. Next, the minimum is found in the entire array starting at index 2, and swapped with the third element.
  4. This goes on until the array to go over has effectively just one element to consider.

In other words, we successively find minimum values and swap them with successive elements in the array, starting with the first element.

The reason why this algorithm is called 'selection sort' is because in each iteration, the next minimum is selected and consequently swapped.

In this exercise, you have to create a function selectionSort() that takes in a given array and sorts it in-place (i.e. the original array must be modified) using the selection sort algorithm.

Note that the function MUST NOT return anything.

View Solution

New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-23-Selection-Sort and put the .html solution files for this exercise within it.

Solution

In the outer loop, with i as its counter variable, we need to iterate from the first to the second last element of the array in search of the correct element for that position.

The last element doesn't need to be considered by this loop since by the time we reach that position, the element sitting there would already be the correct one for that position.

In the inner loop, with j as its counter variable, we need to go from i to the end of the array in search of the minimum to be put at the index i.

This gives us the following code:

function selectionSort(arr) {
   var minIndex;
   var temp;
   var length = arr.length;

   for (var i = 0; i < length; i++) {
      minIndex = i;

      for (var j = i; j < length; j++) {
         if (arr[j] < arr[minIndex]) {
            minIndex = j;
         }
      }

      temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
   }
}

Let's understand the purpose of each variable here:

  • minIndex serves to hold the index of the minimum element found by the inner loop for every ith iteration. Later on this index is used to access the given element of arr and swap it with the ith element.
  • Since swapping is involved, we need a variable to temporarily hold one of the values. That's what temp is there for.
  • length holds the length of arr. It's only purpose is to cache the value of arr.length and thus prevent accessing it again and again in the header of both the given loops.

The statement minIndex = i in line 7 serves to set the ith element as the minimum to start with. After this, the inner loop iterates over the array from j = i to j = length - 1 in search of the minimum. Then this minimum is placed at the ith position.

Let's try this function:

var nums = [5, 9, -10, 5, 0, 1, 10]
undefined
selectionSort(nums)
undefined
nums
[-10, 0, 1, 5, 5, 9, 10]

Improving the code

Although the code above works perfectly, we can add two little things to make it yet more efficient.

  1. The first is to initialize j to i + 1 in the header of the inner loop. This is because the ith element is already considered in the statement minIndex = i in line 7.
  2. The second is to only perform the swap if the elements to be swapped aren't at the same position, i.e. minIndex is not equal to i.

Altogether we get to the following code:

function selectionSort(arr) {
   var minIndex;
   var temp;
   var length = arr.length;

   for (var i = 0; i < length; i++) {
      minIndex = i;


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


      if (minIndex !== i) {
         temp = arr[minIndex];
         arr[minIndex] = arr[i];
         arr[i] = temp;

      }
   }
}