javascript-algorithms/src/algorithms/sorting/shell-sort/ShellSort.js at master · cryptixcoder/javascript-algorithms · GitHub

Repository navigation

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

import Sort from '../Sort';

export default class ShellSort extends Sort {

sort(originalArray) {

// Prevent original array from mutations.

const array = [...originalArray];

// Define a gap distance.

let gap = Math.floor(array.length / 2);

// Until gap is bigger then zero do elements comparisons and swaps.

while (gap > 0) {

// Go and compare all distant element pairs.

for (let i = 0; i < (array.length - gap); i += 1) {

let currentIndex = i;

let gapShiftedIndex = i + gap;

while (currentIndex >= 0) {

// Call visiting callback.

this.callbacks.visitingCallback(array[currentIndex]);

// Compare and swap array elements if needed.

if (this.comparator.lessThan(array[gapShiftedIndex], array[currentIndex])) {

const tmp = array[currentIndex];

array[currentIndex] = array[gapShiftedIndex];

array[gapShiftedIndex] = tmp;

}

gapShiftedIndex = currentIndex;

currentIndex -= gap;

}

}

// Shrink the gap.

gap = Math.floor(gap / 2);

}

// Return sorted copy of an original array.

return array;

}

}