Course: JavaScript

Progress (0%)

# Exercise: Selection Sort

Exercise 26 Easy

Prerequisites for the exercise

1. JavaScript `for` Loop
2. All previous chapters

## Objective

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

## 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 algorithm 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.

## New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-26-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 `i`th iteration. Later on this index is used to access the given element of `arr` and swap it with the `i`th 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 `i`th 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 `i`th 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 `i`th 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;
}
}
}``````

"I created Codeguage to save you from falling into the same learning conundrums that I fell into."

— Bilal Adnan, Founder of Codeguage