Implement insertion sort using JavaScript to sort an array of numbers in ascending order

The art of array sorting is crucial in the world of programming as it allows for efficient organization and manipulation of data. When it comes to implementing a reliable sorting algorithm, insertion sort becomes a versatile and efficient choice. In this article, we delve into the complex world of JavaScript and explore the process of implementing insertion sort to sort an array of numbers in ascending order. By understanding the underlying mechanics of the algorithm and leveraging the power of JavaScript, developers can unlock the potential to efficiently sort and organize numerical data, thereby improving application performance and usability.

Problem Statement

The current challenge involves the task of implementing an insertion sort algorithm using JavaScript to sort an array of numbers in ascending order. The main goal is to design a program that can intelligently rearrange the elements of a given array, ensuring that each subsequent element is placed in the correct position relative to the previous element based on its numerical value. For example, suppose we provide an array

[9, 2, 7, 4, 1]

After executing the insertion sort algorithm, the expected result will be an array following increasing order, such as

[1, 2, 4, 7, 9]

method

In this article we will see a number of different ways to solve the above problems in JavaScript -

• Basic insertion sort

• Binary insertion sort

• Recursive insertion sort

Method 1: Basic insertion sort

The basic insertion sort algorithm maintains a sorted subarray in the array. Starting with the second element, each element is compared to the previous element in the subarray and moved to the right if smaller. This process continues until the correct position is found and the element is inserted. This process is repeated for all elements, resulting in a fully sorted array.

Example

insertionSort function takes the array arr as input and returns an array sorted using the insertion sort algorithm. It iterates starting from the second element and stores it in the current variable. The while loop compares the current element to the previous element in the sorted subarray, moving the larger element to the right. The loop continues until the beginning of the array is reached or a smaller element is found. The current element is then inserted into the sorted subarray at the correct position. This process is repeated for all elements, resulting in a sorted array.

function insertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > current) {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));

Output

The following is the console output -

[ 1, 2, 4, 7, 9 ]

Method 2: Binary insertion sort

The binary insertion sort algorithm improves the efficiency of basic insertion sort by utilizing a binary search in the sorted subarray to determine the correct position of each element. Instead of a linear search, a binary search is performed by comparing the current element to the middle element of the subarray, and adjusting the search bounds accordingly. Once the insertion point is determined, the element is moved to the right to make room, and the current element is inserted. This process is repeated for all elements, resulting in a fully sorted array.

Example

binaryInsertionSort function takes the array arr and returns an array sorted using the binary insertion sort algorithm. It iterates starting from the second element, assuming the first element is sorted. The current element is stored in the current variable. The algorithm performs a binary search in a sorted subarray to find the correct position of the current element by comparing it to the middle element and adjusting the search bounds. Once the position is found, the algorithm moves the element to the right and inserts the current element into the correct position. This process is repeated for all elements, resulting in a sorted array.

function binaryInsertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let left = 0;
      let right = i - 1;
      while (left <= right) {
         let mid = Math.floor((left + right) / 2);
         if (current < arr[mid]) {
            right = mid - 1;
         } else {
            left = mid + 1;
         }
      }
      for (let j = i - 1; j >= left; j--) {
         arr[j + 1] = arr[j];
      }
      arr[left] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));

Output

The following is the console output -

[ 1, 2, 4, 7, 9 ]

Method 3: Recursive insertion sort

The recursive insertion sort algorithm is a recursive version of insertion sort that uses recursion to sort arrays. For subarrays of size 1 or less, it considers them already sorted. For larger subarrays, it calls itself recursively to sort the subarray without the last element. After the recursive call returns and the subarray is sorted, the algorithm places the last element in the correct position in the sorted subarray. This is achieved by comparing the last element to the elements in the sorted subarray and shifting them to the right if necessary. Repeat this process until all elements are inserted into the correct positions, resulting in a fully sorted array.

Example

The recursiveInsertionSort function recursively applies the insertion sort algorithm to the input array. It checks if the array is sorted and returns it if so. Otherwise, it calls itself recursively on a subarray of size n - 1. After being called recursively, the function uses a while loop to compare the last element to the elements in the sorted subarray. If an element is larger, it will be moved to the right. This process continues until the loop reaches the beginning of the array or a smaller element is found. Finally, the last element is inserted at the correct position. This process is repeated for all elements, resulting in a sorted array.

function recursiveInsertionSort(arr, n = arr.length) {
   if (n <= 1) return arr;
 
   recursiveInsertionSort(arr, n - 1);
 
   let last = arr[n - 1];
   let j = n - 2;
 
   while (j >= 0 && arr[j] > last) {
      arr[j + 1] = arr[j];
      j--;
   }
 
   arr[j + 1] = last;
 
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));

Output

The following is the console output -

[ 1, 2, 4, 7, 9 ]

结论

最终，使用 JavaScript 实现插入排序算法以升序排列数字数组，对于寻求熟练排序方法的开发人员来说是一个精明的选择。通过迭代地将元素放置在适当的位置，该算法展示了一种组织数值数据的敏锐方法。虽然插入排序可能不像其他排序技术那样广受好评，但它的效率和简单性使其在某些情况下成为非常宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在其编码库中使用鲜为人知但功能强大的工具，从而生成精简且有序的数组。总之，利用 JavaScript 中插入排序算法的强大功能，对于那些在数组排序中寻求精确性和优雅性的人来说，是一种不切实际的努力。

The above is the detailed content of Implement insertion sort using JavaScript to sort an array of numbers in ascending order. For more information, please follow other related articles on the PHP Chinese website!