/* * Joseph Ryan * jbr2558 * 16200 * Fall 2018 */ package assignment1; import java.util.Arrays; import java.util.stream.IntStream; public class SortTools { /** * This method tests to see if the given array is sorted. * * @param x is the array * @param n is the size of the input to be checked * @return true if array is sorted */ public static boolean isSorted(int[] x, int n) { return IntStream.range(1, n).noneMatch(i -> x[i - 1] > x[i]); } /** * This method returns the index of value v within array x. * * @param x is the array * @param n is the size of the input to be checked * @param v is the value to be searched for within x * @return index of v if v is contained within x. -1 if v is not contained within x */ public static int find(int[] x, int n, int v) { int start = 0, end = n; while (x[start] < v && x[end - 1] >= v) { int half = (start + end) / 2; if (x[half] > v) { end = half; } else { start = half; } } return x[start] == v ? start : -1; } /** * This method returns a newly created array containing the first n elements of x, and v. * * @param x is the array * @param n is the number of elements to be copied from x * @param v is the value to be added to the new array * @return a new array containing the first n elements of x, and v */ public static int[] insertGeneral(int[] x, int n, int v) { if (find(x, n, v) != -1) { return Arrays.copyOf(x, n); } int arr[] = Arrays.copyOf(x, n + 1); arr[n] = v; insertSort(arr, n+1); return arr; } /** * This method inserts a value into the array and ensures it's still sorted * * @param x is the array * @param n is the number of elements in the array * @param v is the value to be added * @return n if v is already in x, otherwise returns n+1 */ public static int insertInPlace(int[] x, int n, int v) { if (find(x, n, v) != -1) return n; x[n] = v; insertSort(x, n + 1); return n + 1; } /** * This method sorts a given array using insertion sort * * @param x is the array to be sorted * @param n is the number of elements of the array to be sorted */ public static void insertSort(int[] x, int n) { for (int i = 1; i < n; i++) { int temp = x[i], j; for (j = i; j > 0 && x[j - 1] > temp; --j) x[j] = x[j - 1]; x[j] = temp; } } }