Selection Sort Algorithm Implementation in JavaScript

Use Case:

The Selection Sort algorithm sorts a dataset by finding the smallest value and moving it to the left of the data structure. When it locates the smallest number from the remainder of the unsorted dataset, it'll swap it with the value that currently resides in the left-most opening.

Here's a description from Wikipedia:

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Here, we're going to implement the Selection Sort algorithm in JavaScript.

1. Swap Values Function

We first need to creater a helper function to help us swap the 2 values in our dataset.

JavaScript

swap = (array, i, j) => { // O(1)
	var temp = array[i]
	array[i] = array[j]
	array[j] = temp
}

The swap function takes the array and the 2 indexes whose values will be swapping places.

2. Selection Sort Function

That's the only helper function we'll need, so now we can loop through our dataset.

JavaScript

selectionSort = array => { // O(n2)
	for (var i = 0; i < array.length; i++) {
		var min = i
		for (var j = i + 1; j < array.length; j++) {
			if (array[j] < array[min]) { min = j }
		}
		if (min !== i) { swap(array,i,min) }
	}
	return array
}

The selectionSort function will take an array and perform a loop for each value in the array. With each loop, the variable min will be reset so we know where we're starting from and which value to swap the identified smallest value with.

Then we'll loop through each value of the array again inside of the current loop starting at the next value in the dataset. During the loop, after we've combed through the entire dataset again, we'll swap the smallest value we found with the value at position min. Then we'll return the array.

Results

JavaScript

var array = [8,3,5,9,1,5,9,2,3,8,4]
selectionSort(array)
// 1,3,5,9,8,5,9,2,3,8,4
// 1,2,5,9,8,5,9,3,3,8,4
// 1,2,3,9,8,5,9,5,3,8,4
// 1,2,3,3,8,5,9,5,9,8,4
// 1,2,3,3,4,5,9,5,9,8,8
// 1,2,3,3,4,5,5,9,9,8,8
// 1,2,3,3,4,5,5,8,9,9,8
// 1,2,3,3,4,5,5,8,8,9,9

The time complexity of the Selection Sort algorithm isn't the best being O(n^2). This algorithm wouldn't be efficient on large lists. The space complexity (at least in this iteration) is very good however, being considered O(1). Because of that, the Selection Sort algorithm may make sense for a program if the dataset isn't too large and you're looking to save memory.

Check out other sorting algorithm implementations in JavaScript:

Tweet me @tylerewillis

Or send me an email: