GeezerVison is showing github.com — feat: insertion sort with binary search (#1182) · Algorithms-Learn/JavaScript@18baef8
File treeExpand file treeCollapse file tree Open diff view settings Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboard +60Lines changed: 60 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +/** | | 2 | + * Pure Implementation of Binary Search Algorithm | | 3 | + * | | 4 | + * Binary insertion sort is a sorting algorithm similar to insertion sort, | | 5 | + * but instead of using linear search to find the position | | 6 | + * where the element should be inserted, we use binary search. | | 7 | + * Thus, we reduce the number of comparisons for inserting one element from O(N) | | 8 | + * (Time complexity in Insertion Sort) to O(log N). | | 9 | + * | | 10 | + */ | | 11 | + | | 12 | +/** | | 13 | + * Search the key element in the array from start position to end position. | | 14 | + * | | 15 | + * @param {Array} array Array of numbers. | | 16 | + * @param {Number} key Value to be searched | | 17 | + * @param {Number} start start index position of array | | 18 | + * @param {Number} end end index position of array | | 19 | + * @return {Number} Position of the key element | | 20 | + */ | | 21 | +function binarySearch (array, key, start, end) { | | 22 | + if (start === end) { | | 23 | + if (array[start] > key) { | | 24 | + return start | | 25 | + } else { | | 26 | + return start + 1 | | 27 | + } | | 28 | + } | | 29 | + | | 30 | + if (start > end) { | | 31 | + return start | | 32 | + } | | 33 | + | | 34 | + const mid = Math.floor((start + end) / 2) | | 35 | + | | 36 | + if (array[mid] < key) { | | 37 | + return binarySearch(array, key, mid + 1, end) | | 38 | + } else if (array[mid] > key) { | | 39 | + return binarySearch(array, key, start, mid - 1) | | 40 | + } else { | | 41 | + return mid | | 42 | + } | | 43 | +} | | 44 | + | | 45 | +/** | | 46 | + * Binary Insertion Sort | | 47 | + * | | 48 | + * @param {Array} list List to be sorted. | | 49 | + * @return {Array} The sorted list. | | 50 | + */ | | 51 | +export function binaryInsertionSort (array) { | | 52 | + const totalLength = array.length | | 53 | + for (let i = 1; i < totalLength; i += 1) { | | 54 | + const key = array[i] | | 55 | + const indexPosition = binarySearch(array, key, 0, i - 1) | | 56 | + array.splice(i, 1) | | 57 | + array.splice(indexPosition, 0, key) | | 58 | + } | | 59 | + return array | | 60 | +} |
Collapse file Copy file name to clipboard +8Lines changed: 8 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +import { binaryInsertionSort } from '../BinaryInsertionSort' | | 2 | + | | 3 | +describe('BinaryInsertionSort', () => { | | 4 | + it('should sort arrays correctly', () => { | | 5 | + expect(binaryInsertionSort([5, 4, 3, 2, 1])).toEqual([1, 2, 3, 4, 5]) | | 6 | + expect(binaryInsertionSort([7, 9, 4, 3, 5])).toEqual([3, 4, 5, 7, 9]) | | 7 | + }) | | 8 | +}) |
|