FilesExpand file tree

 master

/

00binarysort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (55 loc) · 2.01 KB

 master

/

00binarysort.js

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (55 loc) · 2.01 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

61

62

// Basic Knowledge: insertion sort and binary search

// - array search interface: [first, last) range, "less than" relation

// - decompose insertion sort as search part and insert part

// - use binary search at search part

// - use right rotate shift of array as insertion

// - binary search for insertion point: use rightmost of same values

// - sort stability is important attribute of sort implementation

// - ability of imple rotate shift with memmove: system bulk copy function

// binary sort: insertion sort with binary search

// - use array range as [first, last). "last" is not last index.

// - range of entire array is [0, array.length)

var binarySort = function (array, first, last, lessThan) {

for (var i = first + 1; i < last; i += 1) {

var point = binSearch(array, first, i, array[i], lessThan);

cyclicRShift(array, point, i + 1);

}

return array;

};

// binary search for insertion point

var binSearch = function (array, first, last, value, lessThan) {

while (first < last) {

var mid = last + ((first - last) >> 1);

// the condition makes right most point of same values

// leftmost if lessThan become "less than equal"

// rightmost: mid > val

// leftmost: mid >= val

if (lessThan(value, array[mid])) {

last = mid;

} else {

first = mid + 1;

}

}

return first;

};

// 1 right cyclic shift of array range

var cyclicRShift = function (array, first, last) {

if (last - first <= 1) return array;

var mostRight = array[last - 1];

// C: memmove(first, first+1, last-first-1)

for (var cur = last - 1; cur > first; cur -= 1) {

array[cur] = array[cur - 1];

}

array[first] = mostRight;

return array;

};

// builtin less than

var builtinLessThan = function (a, b) {

return a < b;

};

// export interface for runner.js

var sort = this.sort = function (array) {

var lessThan = arguments[1] || builtinLessThan;

binarySort(array, 0, array.length, lessThan);

return array;

};