+/EE422C

software design

git clone https://git.julia.blue/+/EE422C

Joseph RyanProject 1 and quiz 2ead272f

master
2.6 KiB92 linesraw
1/*
2 * Joseph Ryan
3 * jbr2558
4 * 16200
5 * Fall 2018
6 */
7
8package assignment1;
9
10import java.util.Arrays;
11import java.util.stream.IntStream;
12
13public class SortTools {
14    /**
15     * This method tests to see if the given array is sorted.
16     *
17     * @param x is the array
18     * @param n is the size of the input to be checked
19     * @return true if array is sorted
20     */
21    public static boolean isSorted(int[] x, int n) {
22        return IntStream.range(1, n).noneMatch(i -> x[i - 1] > x[i]);
23    }
24
25    /**
26     * This method returns the index of value v within array x.
27     *
28     * @param x is the array
29     * @param n is the size of the input to be checked
30     * @param v is the value to be searched for within x
31     * @return index of v if v is contained within x. -1 if v is not contained within x
32     */
33    public static int find(int[] x, int n, int v) {
34        int start = 0, end = n;
35        while (x[start] < v && x[end - 1] >= v) {
36            int half = (start + end) / 2;
37            if (x[half] > v) {
38                end = half;
39            } else {
40                start = half;
41            }
42        }
43        return x[start] == v ? start : -1;
44    }
45
46    /**
47     * This method returns a newly created array containing the first n elements of x, and v.
48     *
49     * @param x is the array
50     * @param n is the number of elements to be copied from x
51     * @param v is the value to be added to the new array
52     * @return a new array containing the first n elements of x, and v
53     */
54    public static int[] insertGeneral(int[] x, int n, int v) {
55        if (find(x, n, v) != -1) {
56            return Arrays.copyOf(x, n);
57        }
58        int arr[] = Arrays.copyOf(x, n + 1);
59        arr[n] = v;
60        insertSort(arr, n+1);
61        return arr;
62    }
63
64    /**
65     * This method inserts a value into the array and ensures it's still sorted
66     *
67     * @param x is the array
68     * @param n is the number of elements in the array
69     * @param v is the value to be added
70     * @return n if v is already in x, otherwise returns n+1
71     */
72    public static int insertInPlace(int[] x, int n, int v) {
73        if (find(x, n, v) != -1) return n;
74        x[n] = v;
75        insertSort(x, n + 1);
76        return n + 1;
77    }
78
79    /**
80     * This method sorts a given array using insertion sort
81     *
82     * @param x is the array to be sorted
83     * @param n is the number of elements of the array to be sorted
84     */
85    public static void insertSort(int[] x, int n) {
86        for (int i = 1; i < n; i++) {
87            int temp = x[i], j;
88            for (j = i; j > 0 && x[j - 1] > temp; --j) x[j] = x[j - 1];
89            x[j] = temp;
90        }
91    }
92}