+/EE422C
software design
git clone https://git.julia.blue/+/EE422C
ead272f
master
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*/ 21public static boolean isSorted (int []x ,int n ) { 22return 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*/ 33public static int find (int []x ,int n ,int v ) { 34int start =0 ,end =n ; 35while (x [start ] <v &&x [end -1 ] >=v ) { 36int half = (start +end ) /2 ; 37if (x [half ] >v ) { 38end =half ; 39 }else { 40start =half ; 41 } 42 } 43return 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*/ 54public static int []insertGeneral (int []x ,int n ,int v ) { 55if (find (x ,n ,v ) != -1 ) { 56return Arrays .copyOf (x ,n ); 57 } 58int arr [] =Arrays .copyOf (x ,n +1 ); 59arr [n ] =v ; 60insertSort (arr ,n +1 ); 61return 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*/ 72public static int insertInPlace (int []x ,int n ,int v ) { 73if (find (x ,n ,v ) != -1 )return n ; 74x [n ] =v ; 75insertSort (x ,n +1 ); 76return 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*/ 85public static void insertSort (int []x ,int n ) { 86for (int i =1 ;i <n ;i ++) { 87int temp =x [i ],j ; 88for (j =i ;j >0 &&x [j -1 ] >temp ; --j )x [j ] =x [j -1 ]; 89x [j ] =temp ; 90 } 91 } 92}