Insertion Sort Algorithm explaination

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It iterates through the given array and, at each iteration, it takes an element and inserts it into the correct position in the already sorted part of the array.

Here’s how the Insertion Sort algorithm works:

1. Start from the second element (index 1) of the array since the first element (index 0) is considered initially as a sorted part of the array.
2. Iterate through the array: For each element in the unsorted part of the array, compare it with the elements in the sorted part of the array, moving larger elements one position to the right to make space for the current element.

Execution process of insertion process

Let’s apply the Insertion Sort algorithm to the array [4, 23, 7, 39, 19, 9, 14]:

Initial array: [4, 23, 7, 39, 19, 9, 14]

1. Pass 1: Consider the second element (23). Compare it with the first element (4). Since 23 is greater than 4, no swap is needed in this case. So, the array remains [4, 23, 7, 39, 19, 9, 14].
2. Pass 2: Consider the third element (7). Compare it with 23 and then 4. 7 is smaller than 23, so 23 shifts to the right. 7 is also smaller than 4, so 4 shifts to the right. Finally, place 7 in the correct position. The array becomes [4, 7, 23, 39, 19, 9, 14].
3. Pass 3: Consider the fourth element (39). It is larger than 23, so no shifting is needed. The array remains [4, 7, 23, 39, 19, 9, 14].
4. Pass 4: Consider the fifth element (19). Compare it with 39, then 23, and then 7. 19 is smaller than 39, so 39 shifts to the right. 19 is also smaller than 23, so 23 shifts to the right. Lastly, 19 is larger than 7, so it stays to the right of 7. The array becomes [4, 7, 19, 23, 39, 9, 14].
5. Pass 5: Consider the sixth element (9). Compare it with 39, 23, 19, and 7. 9 is smaller than all these elements. So, 39, 23, 19, and 7 shift to the right, creating space for 9. The array becomes [4, 7, 9, 19, 23, 39, 14].
6. Pass 6: Consider the seventh element (14). Compare it with 39, 23, 19, 9, and 7. 14 is smaller than 39, so 39 shifts to the right. Similarly, 14 is smaller than 23, so 23 shifts to the right. 19 is also larger than 14, so it shifts to the right. 9 and 7 are also larger than 14, so they shift to the right. Finally, place 14 in the correct position. The final sorted array becomes [4, 7, 9, 14, 19, 23, 39].

Insertion Sort algorithm

/**
 * @approach Align small digit to big digit [0 -> 4 -> 7 -> 9 -> ...]
 * @complexity
 * - Time complexity: O(n2); Call: Worst Case: Order of n square, Best Case: Order of n
 * - Space complexity: O(1); Call: Order of 1
 */
function insertionSort(arr: number[]): number[] {
  let item: number,
    i: number = 1,
    j: number;
  for (i; i < arr.length; i++) {
    item = arr[i];
    j = i - 1;

    while (j >= 0 && arr[j] > item) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = item;
  }
  return arr;
}

const arr = [4, 23, 7, 39, 19, 9, 14];
console.log(insertionSort(arr)); // [4,  7,  9, 14, 19, 23, 39]

This completes the Insertion Sort algorithm for the given array, and now the array is sorted in ascending order.