Insertion Sort

Insertion Sort is a sorting algorithm that is slightly more efficient than Bubble sort, although both has the same Big O complexity in theory.

The algorithm works by taking each element and inserting it into its correct position within the already sorted portion of the array, continuing this process untill all elements are sorted.

Insertion Sort 與 Bubble sort 相比稍微有效率，但兩者的 Big O 值相同
此演算法藉由不斷將未排序的元素插入到已排序完成的部分內的正確位置，直到所有元素都被排序好

Steps of Insertion sort

這裡用 小 => 大 排序做說明

1. Start
   Start with the first element.
   If the dataset contains only one element, it is already sorted.
   如果 dataset 內只有一個元素，則視作已排序好（不需要去排第1個元素）
2. Move to the next element
   Move to second element and compare value of first element and second element.
   移動到下一個元素，並將第2個元素跟第1個做比較
3. Insert into correct position
   Insert the second element into correct position by shifting larger elements to the right.
   如果第2個元素比第1個值小，則將第2個元素插入到第1個元素左邊
4. Repeat
   Move to the next element and repeat the comparison and insertion step untill all elements are considered.
   不斷重複先前的步驟，將第3個元素跟第2,第1個元素比較，並插入到其正確的位置
5. End
   Continue untill the entire array is sorted.
   當所有元素都被排序好，Insertion Sort 則結束

Complexity of insertion sort

跟 Bubble sort 一樣，為 O(n^2)

Implementation of insertion sort

• i start from array[1], due to array[0] is already sorted

let unsortedArr = [8, 3, 6, 5, 7, 1];

function insertationSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let currentIndex = i;

        while (
            currentIndex > 0 &&
            arr[currentIndex - 1] > arr[currentIndex]
        ) {
            // do swap
            [arr[currentIndex - 1], arr[currentIndex]] = [
                arr[currentIndex],
                arr[currentIndex - 1],];
            currentIndex--;
        }
    }
    return arr;
}
console.log(insertationSort(unsortedArr); 

相關資源

insertion sort
https://www.w3schools.com/dsa/dsa_algo_insertionsort.php
insertion sort
https://www.geeksforgeeks.org/insertion-sort-algorithm/
insertion-sort
https://big-o.io/algorithms/comparison/insertion-sort/