Hello! In this post, we will learn how to solve algorithm problems using JavaScript. The topic is ‘Insertion Sort’. All algorithms are means to solve specific problems, and insertion sort is one of the most fundamental and important sorting algorithms. Through this article, we will understand the concept of insertion sort and explore in detail how to implement it in JavaScript.
1. What is Insertion Sort?
Insertion sort is a very efficient sorting algorithm when the data is nearly sorted. This algorithm basically divides the list into two parts and builds a sorted list by inserting new elements into their appropriate positions. It has a methodology of comparing each element one by one and inserting it into its rightful place.
1.1. How Insertion Sort Works
The basic process of insertion sort works as follows:
- Compare the first two elements.
- If the first element is greater than the second element, swap their positions.
- Select the next element and appropriately insert it into the sorted list. Repeat this process until all elements are sorted.
2. Time Complexity of Insertion Sort
The average time complexity of insertion sort is O(n²). Even in the worst case, it remains O(n²), and it only shows O(n) performance in the best case. However, the best case occurs when the data is already sorted. For this reason, insertion sort is very efficient for cases with a small number of elements or nearly sorted data.
3. Problem Definition
3.1. Problem Statement
Given an integer array like the following, write a function to sort the array in ascending order using insertion sort.
Input: [5, 2, 9, 1, 5, 6]
Output: [1, 2, 5, 5, 6, 9]
4. Algorithm Implementation
Now let’s actually implement insertion sort in JavaScript. The code is simple and is as follows:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
// Compare the current key with the sorted part to find position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Move position
j--;
}
arr[j + 1] = key; // Insert position
}
return arr;
}
// Test
const input = [5, 2, 9, 1, 5, 6];
console.log(insertionSort(input)); // [1, 2, 5, 5, 6, 9]
4.1. Code Explanation
The above code is structured as follows:
- for loop: Starts from the second element of the array (index 1) and iterates to the last element of the array.
- key variable: This is the element that is currently used as a reference. This value will be inserted into the sorted array.
- while loop: Compares the current element (key) with the sorted part (left) to find its position. Moves larger elements to the right.
- Inserts each element into its appropriate position and ultimately returns the sorted array.
5. Performance Analysis
The performance of insertion sort depends on the composition of the input data, but it generally has an average speed of O(n²) for an array of length n. It is very simple, but it does not perform well on large datasets, so it is common to use it alongside other sorting algorithms in practical applications.
6. Advantages and Disadvantages of Insertion Sort
6.1. Advantages
- It can be easily implemented.
- It is very fast when the data is nearly sorted.
- It uses little memory and does not require additional space.
- It is a stable sorting algorithm.
6.2. Disadvantages
- It is inefficient for large datasets.
- With a time complexity of O(n²), it performs poorly in the worst case.
7. Conclusion
In this post, we learned about insertion sort. It is a simple sorting algorithm, but understanding and utilizing its structure and working mechanism is very useful. In particular, it is a fundamental algorithm you must know when writing advanced algorithms in JavaScript. In the next tutorial, we will compare it with other sorting algorithms to further expand your understanding of algorithms!