mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 15:39:42 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
63 lines
2.1 KiB
JavaScript
63 lines
2.1 KiB
JavaScript
/* 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
|
|
}
|