title: Selection Sort and Insertion Sort in JavaScript Sorting Algorithms
date: 2018-12-2 20:01:37
banner: http://img.yanyuanfe.cn/algorithm.jpg
tags:
- algorithm
Learning data structures and algorithms helps in writing more efficient code.
Basics determine the heights you can possibly reach, while business determines your lowest bottleneck.
Understanding and learning commonly used JavaScript algorithms can help front-end developers write more efficient code. This article introduces two sorting algorithms with a time complexity of O(n^2): selection sort and insertion sort.
Selection Sort#
The principle of selection sort is: traverse the sorted array, and during the traversal, traverse the array after the current index to find the index of the smallest element. Then, swap the element at the current index with the element at the index of the smallest element.
function swap(arr, a, b) {
[arr[a], arr[b]] = [arr[b], arr[a]];
}
function selectionSort(arr) {
for (let i = 0, len = arr.length; i < len; i ++) {
let minIndex = i;
for(let j = i + 1; j < len; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
Selection sort has a time complexity of O(n^2) because it has nested loops.
Insertion Sort#
The principle of insertion sort is similar to organizing cards in ascending order while playing poker. Start traversing from the first item in the array, and during the traversal, compare the current index with the elements on its left side from right to left. If the element on the left side is greater than the element on the right side, swap them. Otherwise, exit the current loop. The code implementation is as follows:
function insertionSort(arr) {
// Start from 1
for (let i = 1, len = arr.length; i < len; i ++) {
// Find the appropriate position to insert the element
for (let j = i; j > 0; j --) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
} else {
break; // Exit the current loop
}
}
}
}
In the inner loop, the comparison of two elements' sizes can be placed inside the for loop to simplify the code.
function insertionSort(arr) {
// Start from 1
for (let i = 1, len = arr.length; i < len; i ++) {
// Find the appropriate position to insert the element
for (let j = i; j > 0 && arr[j] < arr[j - 1]; j --) {
swap(arr, j, j - 1);
}
}
}
Comparing selection sort and insertion sort, both of them have two nested loops and a time complexity of O(n^2). However, from the code, insertion sort terminates the inner loop earlier. Does this mean that insertion sort is faster than selection sort?
Test Sorting Time#
Now let's test the two sorting algorithms to verify if insertion sort is faster than selection sort.
Here, we use console.time and console.timeEnd to test the time consumed by a piece of code. console.time starts the timer, and console.timeEnd stops the timer and outputs the execution time of the code. They are used as follows:
// Start the timer
console.time('test');
// Code to be tested
// Stop the timer and output the time
console.timeEnd('test');
// test:4522.303ms
These two methods take a parameter as the name of the timer.
Write the test code as follows:
function testFuncTime(tag, fn, args) {
console.time(tag);
fn(args);
console.timeEnd(tag);
}
testFuncTime takes three parameters: the name of the timer, the method to be tested, and the arguments of the method.
To make the test results more obvious, we need a method that can generate an array of random numbers within a certain range.
function getRandom(start, end, n) {
let arr = [];
for(let i=0; i<n; i++) {
let choice = end - start + 1;
let value = Math.floor(Math.random() * choice + start);
arr.push(value);
}
return arr;
}
Write the getRandom method to generate an array of n random numbers between start and end.
Here is the test code:
let array = getRandom(1, 10000, 1000);
let array2 = [...array];
testFuncTime('selectionSort', selectionSort, array);
testFuncTime('insertionSort', insertionSort, array2);
console.log(array);
console.log(array2);
In the above code, we generate an array called array with 1000 random numbers ranging from 1 to 10000, and make a copy of it called array2. Then, we run testFuncTime to test the sorting algorithms and output the sorting results.
The results are as follows:
We can see that the time taken by insertion sort is approximately three times that of selection sort, which is contrary to our expectations. So, what is the reason?
The reason is that selection sort only needs one swap operation to find the index of the smallest value during the inner loop. However, insertion sort compares and swaps from right to left in the inner loop, and swapping is the most time-consuming operation.
Now let's optimize the implementation of insertion sort.
Optimize Insertion Sort#
function insertionSort(arr) {
// Start from 1
for (let i = 1, len = arr.length; i < len; i ++) {
// Find the appropriate position to insert the element
let e = arr[i];
let j; // j saves the position where element e should be inserted
for (j = i; j > 0 && arr[j - 1] > e; j --) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
In the above code, we optimize insertion sort. In the outer loop, we first declare a variable e to save the current element, and declare a variable j to save the position where element e should be inserted. In the inner loop, if the element on the left side is greater than the current element, we assign the element on the left side to the current element, and variable j keeps moving to the left until the loop ends. Finally, we assign the element e to arr[j].
We have declared a new variable and used assignment instead of swapping to optimize performance. Now let's test the optimized code.
From the above image, we can see that the optimized insertion sort takes about half the time of selection sort, showing a significant improvement in performance.
Conclusion#
This article uses JavaScript to implement two sorting algorithms with a time complexity of O(n^2). For selection sort, its disadvantage is that both nested loops must be fully executed, so its efficiency is very slow under any condition. In contrast, although insertion sort has a worst-case complexity of O(n^2), in practical applications, sorting algorithms with a complexity of O(n^2) are not useless. They can be optimized as sub-processes of more complex sorting algorithms. Moreover, for nearly sorted arrays (such as system logs generated by time), insertion sort is faster than sorting algorithms with a complexity of O(nlogn). In completely sorted arrays, the complexity of insertion sort can reach O(n).