FilesExpand file tree

 master

/

ShellSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

48 lines (41 loc) · 1.08 KB

 master

/

ShellSort.java

Top

File metadata and controls

• Code
• Blame

48 lines (41 loc) · 1.08 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

package Sorts;

import static Sorts.SortUtils.*;

public class ShellSort implements SortAlgorithm {

/**

* Implements generic shell sort.

*

* @param array the array to be sorted.

* @param <T> the type of elements in the array.

* @return the sorted array.

*/

@Override

public <T extends Comparable<T>> T[] sort(T[] array) {

int length = array.length;

int gap = 1;

/* Calculate gap for optimization purpose */

while (gap < length / 3) {

gap = 3 * gap + 1;

}

for (; gap > 0; gap /= 3) {

for (int i = gap; i < length; i++) {

int j;

T temp = array[i];

for (j = i; j >= gap && less(temp, array[j - gap]); j -= gap) {

array[j] = array[j - gap];

}

array[j] = temp;

}

}

return array;

}

/* Driver Code */

public static void main(String[] args) {

Integer[] toSort = {4, 23, 6, 78, 1, 54, 231, 9, 12};

ShellSort sort = new ShellSort();

sort.sort(toSort);

for (int i = 0; i < toSort.length - 1; ++i) {

assert toSort[i] <= toSort[i + 1];

}

print(toSort);

}

}