FilesExpand file tree

 master

/

BinaryInsertionSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (55 loc) · 1.54 KB

 master

/

BinaryInsertionSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (55 loc) · 1.54 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

/**

* Pure Implementation of Binary Search Algorithm

*

* Binary insertion sort is a sorting algorithm similar to insertion sort,

* but instead of using linear search to find the position

* where the element should be inserted, we use binary search.

* Thus, we reduce the number of comparisons for inserting one element from O(N)

* (Time complexity in Insertion Sort) to O(log N).

*

*/

/**

* Search the key element in the array from start position to end position.

*

* @param {Array} array Array of numbers.

* @param {Number} key Value to be searched

* @param {Number} start start index position of array

* @param {Number} end end index position of array

* @return {Number} Position of the key element

*/

function binarySearch (array, key, start, end) {

if (start === end) {

if (array[start] > key) {

return start

} else {

return start + 1

}

}

if (start > end) {

return start

}

const mid = Math.floor((start + end) / 2)

if (array[mid] < key) {

return binarySearch(array, key, mid + 1, end)

} else if (array[mid] > key) {

return binarySearch(array, key, start, mid - 1)

} else {

return mid

}

}

/**

* Binary Insertion Sort

*

* @param {Array} list List to be sorted.

* @return {Array} The sorted list.

*/

export function binaryInsertionSort (array) {

const totalLength = array.length

for (let i = 1; i < totalLength; i += 1) {

const key = array[i]

const indexPosition = binarySearch(array, key, 0, i - 1)

array.splice(i, 1)

array.splice(indexPosition, 0, key)

}

return array

}