SortingAlgorithms/BinaryInsertionSort.java at master · Cselwood/SortingAlgorithms · GitHub

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.Arrays;

public class BinaryInsertionSort {

    String complexity;

    BinaryInsertionSort() {

        complexity = ". O(log2(n)) Time Complexity.";

    }

    void sort(int[] sortArray) {

        /*
        Begin Time Start
         */
        double start = (double) System.nanoTime();

        int location, select;
        int foobar;

        for (int count = 1; count < sortArray.length; count++) {

            foobar = count - 1;
            select = sortArray[count];

            location = binaryInsertionSort(sortArray, select, 0, foobar);

            while (foobar >= location) {

                sortArray[foobar + 1] = sortArray[foobar];
                foobar--;

            }

            sortArray[foobar + 1] = select;

        }

        /*
        End Time
         */
        double end = (double) System.nanoTime();

        System.out.println("BinaryInsertionSort: " + Arrays.toString(sortArray) + complexity + " Seconds taken was " + ((end - start) / 1000000));
    }

    int binaryInsertionSort(int[] sortArray, int select, int lower, int upper) {

        if (upper <= lower) {

            if (select > sortArray[lower]) {

                return (lower + 1);

            }
            else {

                return lower;

            }

        }

        int middle = (lower + upper) / 2;

        if (select == sortArray[middle]) {

            return (middle + 1);

        }

        if (select > sortArray[middle]) {

            return binaryInsertionSort(sortArray, select, (middle + 1), upper);

        }

        return binaryInsertionSort(sortArray, select, lower, (middle - 1));

    }

}