Improve insertion sort algorithm and its description

Andrea Tota · Andrea Tota · commit 66b83ad2c4e2 · 2022-03-03T18:38:50.000+01:00
diff --git a/Sorts/InsertionSort.js b/Sorts/InsertionSort.js
@@ -1,21 +1,45 @@
-/* In insertion sort, we divide the initial unsorted array into two parts;
-* sorted part and unsorted part. Initially the sorted part just has one
-* element (Array of only 1 element is a sorted array). We then pick up
-* element one by one from unsorted part; insert into the sorted part at
-* the correct position and expand sorted part one element at a time.
+/**
+ * @function InsertionSort
+ * @description Quick sort is a stable sorting algorithm
+ * @param {Integer[]} array - Array of integers
+ * @return {Integer[]} - Sorted array
+ * @see [InsertionSort](https://en.wikipedia.org/wiki/Quicksort)
+ */
+
+/*
+  * Big-O Analysis
+      * Time Complexity
+        - O(N^2) on average and worst case scenario
+        - O(N) on best case scenario (when input array is already almost sorted)
+      * Space Complexity
+        - O(1)
 */
-export function insertionSort (unsortedList) {
-  const len = unsortedList.length
-  for (let i = 1; i < len; i++) {
-    let j
-    const tmp = unsortedList[i] // Copy of the current element.
-    /* Check through the sorted part and compare with the number in tmp. If large, shift the number */
-    for (j = i - 1; j >= 0 && (unsortedList[j] > tmp); j--) {
-      // Shift the number
-      unsortedList[j + 1] = unsortedList[j]
+
+/* In insertion sort, we divide the initial unsorted array into two parts;
+ * sorted part and unsorted part. Initially the sorted part just has one
+ * element (Array of only 1 element is a sorted array). We then pick up
+ * element one by one from unsorted part; insert into the sorted part at
+ * the correct position and expand sorted part one element at a time.
+ */
+
+export function insertionSort (array) {
+  const length = array.length
+  if (length < 2) return array
+
+  for (let i = 1; i < length; i++) {
+    // Take current element in array
+    const currentItem = array[i]
+    // Take index of previous element in array
+    let j = i - 1
+
+    // While j >= 0 and previous element is greater than current element
+    while (j >= 0 && array[j] > currentItem) {
+      // Move previous, greater element towards the unsorted part
+      array[j + 1] = array[j]
+      j--
     }
-    // Insert the copied number at the correct position
-    // in sorted part.
-    unsortedList[j + 1] = tmp
+    // Insert currentItem number at the correct position in sorted part.
+    array[j + 1] = currentItem
   }
+  return array
 }
diff --git a/Sorts/test/InsertionSort.test.js b/Sorts/test/InsertionSort.test.js
@@ -0,0 +1,19 @@
+import { insertionSort } from '../InsertionSort'
+
+describe('insertionSort', () => {
+  it('expects to work with empty array', () => {
+    expect(insertionSort([])).toEqual([])
+  })
+
+  it('expects to return input array when array.length is less than 2', () => {
+    const input = [3]
+    expect(insertionSort(input)).toEqual(input)
+  })
+
+  it('expects to return array sorted in ascending order', () => {
+    expect(insertionSort([14, 11])).toEqual([11, 14])
+    expect(insertionSort([21, 22, 23])).toEqual([21, 22, 23])
+    expect(insertionSort([1, 3, 2, 3, 7, 2])).toEqual([1, 2, 2, 3, 3, 7])
+    expect(insertionSort([1, 6, 4, 5, 9, 2])).toEqual([1, 2, 4, 5, 6, 9])
+  })
+})
