A Voyage through Algorithms using Javascript - Insertion Sort

What is Insertion Sort?

Insertion Sort is another fundamental sorting algorithm in computer science. It builds the final sorted array one item at a time. It's much like sorting a hand of playing cards - you pick up cards one by one and insert each into its proper position among the cards you've already sorted.

How Insertion Sort Works

Insertion Sort iterates through the array, growing the sorted portion with each iteration. For each element, it compares it with the already sorted elements, moving them up until it finds the correct position to insert the current element.

Here's a step-by-step breakdown:

1. Start with the second element (index 1) as the "current" element.
2. Compare the current element with the one before it.
3. If the current element is smaller, compare it with the elements before. Move the greater elements up to make space for the swapped element.
4. Repeat steps 2-3 until the whole array is sorted.

Visualization of Insertion Sort:

Recorded gif from https://visualgo.net/en/sorting

Implementing Insertion Sort in JavaScript

Let's take a look at the implementation of Insertion Sort in JavaScript, with detailed comments explaining each part:

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

Key Points:

1. Two-Directional Process: Insertion Sort operates through a forward-moving outer loop and a backward-looking inner loop, creating a back-and-forth movement that forms the core of the algorithm.
2. Forward Scan (Outer Loop):

   for (let i = 1; i < arr.length; i++)

Moves forward through the array, selecting one unsorted element (currentElement = arr[i]) at a time.

1. Backward Insert (Inner Loop):

   while (j >= 0 && arr[j] > currentElement)

Looks backward into the sorted portion, shifting larger elements right (arr[j 1] = arr[j]) to make room for the current element.

1. Element Insertion:

   arr[j + 1] = currentElement;

Inserts the current element into its correct position, growing the sorted portion.

1. In-Place and Stable Sorting: Modifies the original array directly, maintaining the relative order of equal elements.

Insertion Sort builds the final sorted array one item at a time, mimicking how you'd sort a hand of cards. It repeatedly selects a card (element) from the unsorted portion and inserts it into its correct position among the sorted cards, shifting larger cards as needed. This intuitive process makes Insertion Sort efficient for small or nearly-sorted datasets.

Is Insertion Sort Stable?

Yes, Insertion Sort is a stable sorting algorithm. Stability in sorting algorithms means that the relative order of equal elements is preserved after sorting. Insertion Sort achieves this naturally due to its method of operation:

1. Preserving Order: When inserting an element into the sorted portion, Insertion Sort only shifts elements that are strictly greater than the current element. This means that if there are multiple elements with the same value, their relative order will be maintained.
2. No Unnecessary Swaps: Unlike some other sorting algorithms that might swap equal elements, Insertion Sort only moves an element when necessary. This characteristic ensures that equal elements remain in their original relative positions.
3. Left-to-Right Processing: By processing the array from left to right and inserting each element into its correct position among the already-sorted elements, Insertion Sort naturally maintains the original order of equal elements.

The stability of Insertion Sort can be particularly useful when sorting complex data structures where maintaining the original order of equal elements is important. For example, when sorting a list of students first by grade and then by name, a stable sort would ensure that students with the same grade remain in alphabetical order by name.

This stability is an inherent property of the basic Insertion Sort algorithm and doesn't require any additional modifications or overhead to achieve, making it a naturally stable sorting method.

Time and Space Complexity Analysis

Insertion Sort's performance characteristics are as follows:

• Time Complexity:

  • Best Case: O(n) - when the array is already sorted
  • Average Case: O(n^2)
  • Worst Case: O(n^2) - when the array is reverse sorted

• Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm

与选择排序不同，插入排序可以在近排序数组上表现良好，在这种情况下实现接近线性的时间复杂度。

插入排序的优点和缺点

优点：

• 易于实施和理解
• 对于中小型数据集非常有效
• 自适应 - 在近排序数组上表现良好
• 稳定 - 保持相等元素的相对顺序
• 就地排序（O(1) 空间）
• 适合在线排序场景

缺点：

• 大型数据集效率低下（平均和最坏情况下为 O(n^2)）
• 随着输入大小的增加，性能会迅速下降

何时使用插入排序

• 中小型数据集（通常最多几百个元素）
• 接近排序的数据
• 在线排序场景，元素被增量接收并排序
• 作为更复杂算法中的子例程（例如，小分区的快速排序）

实际应用和用例

1. 标准库实现：通常用于小型数组或作为混合排序算法的一部分
2. 数据库操作：对小组记录进行排序
3. 嵌入式系统：由于其简单性和低内存开销，适合资源有限的系统
4. 实时数据处理：在接收数据时保持排序顺序

结论

插入排序尽管对于大型数据集有局限性，但在特定场景中提供了宝贵的优势。它的直观性，类似于我们手动对卡片进行排序的方式，使其成为理解排序算法的优秀教育工具。

要点：

• 几乎排序数据的最佳情况时间复杂度为 O(n)
• 稳定、就地、自适应的排序算法
• 对于小型数据集和在线排序非常有效
• 经常纳入混合排序策略

虽然不适合大规模排序任务，但插入排序的原理通常应用于更复杂的方法中。它在某些场景下的简单性和高效性使其成为程序员算法工具包的宝贵补充。

排序算法的选择最终取决于您的具体用例、数据特征和系统约束。了解插入排序可以深入了解算法设计权衡，并为探索更高级的排序技术奠定基础。

The above is the detailed content of A Voyage through Algorithms using Javascript - Insertion Sort. For more information, please follow other related articles on the PHP Chinese website!