Introduction to Insertion Sort in JavaScript
Sorting is one of the important concepts that programmers learn to begin their journey in computer science irrespective of the programming language selected to learn. Sorting helps us to locate the target data we want to search in a faster and convenient manner, by sorting them in either ascending or descending order.
Sorting algorithms are used to reorder elements, where an element can be a number or a string. There are many types of sorting algorithms based on their method of sorting and the approach they follow to sort the elements, and each type has its advantages and disadvantages.
In this blog, we will be focusing on insertion sort, a common sort that is easy to understand and implement.
What is Insertion Sort in JavaScript?
Insertion Sort is a simple, easy to understand the algorithm that works best with a small data list by sorting each element in the data list one by one from left to right direction. It is also known as a comparison sort where it compares the current value with the other values within the same data list that’s being sorted. It follows an iterative approach to place each element in the right order in the data list.
The more time an algorithm takes to sort, its performance is said to be bad and need to consider another algorithm to sort out the data. Insertion sort has a time complexity of O(n²) or runs quadratic time to sort the data list in the worst-case scenario. This typically isn’t very effective and should not be used for large lists. However, it usually outperforms advanced algorithms such as quicksort or mergesort on smaller lists.
Insertion sort, most of the time is more efficient than other quadratic sorting algorithms such as bubble sort or selection sort. Its best-case scenario, time is O(n), or linear, which occurs if the input array is already sorted. On average, insertion sort’s run time is still quadratic.
In the below example we will have an easy high-level approach to sort data stored in an array data structure and use its sort method to sort the data without implementing any algorithms.
Example – Insertion Sort Algorithm
Code:
<!DOCTYPE html>
<html>
<body>
</body>
<script>
// Declaring unsorted data and storing it in array data structure
var dataArray = [96,5,42,1,6,37,21]
// Function - Insertion Sort Algo.
function insertSort(unsortedData) {
for (let i = 1; i < unsortedData.length; i++) {
let current = unsortedData[i];
let j;
for(j=i-1; j >= 0 && unsortedData[j] > current;j--) {
unsortedData[j + 1] = unsortedData[j]
}
unsortedData[j + 1] = current;
}
return unsortedData;
}
// print sorted array
console.log(insertSort(dataArray));
</script>
</html>Output:
Explanation: In the algorithm, we have implemented 2 for loops, the outer for loop is to iterate over the array elements and the inner for loop is used to sort the array elements in the ascending order of their value. The current variable holds the current value of the array and variable j is set to one value less than the current index position of the array. We check whether the current element (current) is smaller than the array value at jth position (unsortedData[j])and if it is true then we sort those values.
Iteration 1 – current (96) : [96,5,42,1,6,37,21]
Iteration 2 – current (5) : [5,96,42,1,6,37,21]
Iteration 3 – current (42) : [5,42,96,1,6,37,21]
Iteration 4 – current (1) : [1,5,42,96,6,37,21]
Iteration 5 – current (6) : [1,5,6,42,96,37,21]
Iteration 6 – current (37) : [1,5,6,37,42,96,21]
Iteration 7 – current (21) : [1,5,6,21,37,42,96]
The outer for loop iteration starts at 1st index position since we want to move the smallest element to the left hand side so we are comparing whether the current element is smaller than the elements on its left hand side.
Types of Sorting
The types of algorithms that are used for sorting data encompasses the following concepts or ideas in their approach to sorting the data:
- Comparison versus non-comparison-based strategies,
- Iterative versus Recursive implementation,
- Divide-and-Conquer paradigm (this or that),
- Randomize Approach.
Let’s consider a few examples:
1. Merge sort uses a divide-and-conquer approach to sort elements in an array.
2. Insertion Sort, Bubble Sort is a comparison-based sort.
When data is sorted, it becomes easier to come up with an optimal solution to complex problems. for example,
- Searching for a specific value,
- Finding the minimum or maximum value,
- Testing for uniqueness and deleting duplicates,
- Counting how many times a specific value has appeared, etc.
Conclusion
In this article, we have gone through the definition of insertion sort and its time complexity and various other sorting algorithm types based on their approach. Studying various sorting algorithms helps us to identify which one is better suited at certain circumstances or use cases that help us to sort the data at a faster rate.
Recommended Articles
This is a guide to Insertion Sort in JavaScript. Here we discuss what is insertion sort in javascript and its types with example respectively. You may also look at the following articles to learn more –
