/* 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(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]
    }
    // Insert the copied number at the correct position
    // in sorted part.
    unsortedList[j + 1] = tmp
  }
}

/**
 * @function insertionSortAlternativeImplementation
 * @description InsertionSort 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 insertionSortAlternativeImplementation(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 currentItem number at the correct position in sorted part.
    array[j + 1] = currentItem
  }
  // Return array sorted in ascending order
  return array
}