Description
For this project, you will write a few functions that create and manipulate sorted
arrays of integers. This is an individual assignment.
You will be provided with a “test program” with a couple of simple test cases,.
Part of this assignment is to reasonably interpret/understand the specification, as
well as designing and validating a solution.
For this particular assignment, you may post ideas about testing to Piazza, in as
much detail as you wish. Do not post testcase code, and do not post solution
code (except a line, perhaps, to ask about syntax, for example). Your testcase
ideas should not hint at the solution algorithm.
Instructions:
Design, implement and validate a Java class called SortTools that has public
static methods for each of the following functions. You may not use the static
methods in java.util.Arrays or Java Collections in your solution, except, if you
want, Arrays.copyOf and Arrays.copyOfRange. (Both these copy methods
are not essential for the solution.) In all the cases below, there will be no
illegal inputs, that don’t make sense. For example, negative n, or n >
x.length.
• boolean isSorted(int[] x, int n) – returns true if the first n elements of x
are sorted in non-decreasing order, returns false otherwise. The
contents of x are not modified by this function.
o The worst case time complexity of this function should be O(n).
o Precondition: n <= x.length, n >= 0.
o If x.length = 0 or n = 0, return false.
o Precondition: x will not be null.
• int find(int[] x, int n, int v) – if v is contained within the first n elements of
x, return an index of v (i.e. return k where x[k] == v and k < n – if there
are multiple such values for k, then your function must return one of
those values, but may return any k < n where x[k] == v). If v is not
contained within the first n elements of x return -1. The contents of x
are not modified by this function.
o Precondition: x must be sorted in non-decreasing order. If this
precondition is not satisfied, then the result of calling find is
undefined and may produce catastrophic behavior.
o Precondition: x will not be null.
o Precondition: n <= x.length, n > 0.
o The worst case time complexity of find should be O(log n)
• int[] insertGeneral(int[] x, int n, int v) – return a newly created array of
integers with the following properties.
8/26/17 2
o The contents of the new array include the first n elements of x
and the value v.
o The contents of the new array are sorted in non-decreasing
order.
o If the first n elements of x contain at least one copy of the value
v, then the new array will contain n values (i.e. do not add
another copy of v if it is already in x).
o If the first n elements of x do not contain v then the new array
will contain n+1
values (i.e. the original contents plus v).
o Precondition: x must be sorted in non-decreasing order. If this
precondition is not satisfied, then the result of calling this
function is undefined and may produce catastrophic behavior.
o Precondition: n <= x.length, and n >= 0.
o Precondition: x != null.
o Precondition:x.length > 0.
o The worst case time complexity should be O(n).
• int insertInPlace(int[] x, int n, int v) – modify x so that it satisfies the
following properties:
o If x contained at least one copy of the value v within the first n
elements (array elements x[0..n-1]) prior to executing the
function, then x is not modified, and n is returned by the function.
o Otherwise the modified array will contain the first n values from
the original array and the value v. These n+1 values are sorted
in non-decreasing order and stored in array elements x[0..n].
The function returns n+1. The remaining elements of x (i.e. the
elements after index n) are “don’t care”.
o Precondition: x.length is at least n + 1. If this precondition is
not satisfied, then the result of calling this function is undefined
and may produce catastrophic behavior.
o Precondition: x must be sorted in non-decreasing order. If this
precondition is not satisfied, then the result of calling this
function is undefined and may produce catastrophic behavior.
o Precondition: n > 0. n < x.length.Precondition: x.length > 0.
o The worst case time complexity should be O(n).
• void insertSort(int[] x, int n) – sort the first n elements of x in nondecreasing order. You must obtain the following time complexity
bounds:
o In the general case, your function must have O(n2) time
complexity (i.e. scale no worse than quadratically in n).
o In the special case that x is nearly sorted, your function must
have O(n) time complexity. The formal definition of nearly sorted
is: x[k] ≤ x[k+1] for all 0 ≤ k < n, except for at most C values of k
(where C is a constant).
o Informally, your function must have linear time complexity if all
the elements in x are sorted with just one value out of place.
o You have choices of algorithm based on the above criteria
alone, but we want you to implement insertion sort.
8/26/17 3
o Precondition: x.length > 0, n > 0, n <= x.length.
o Precondition: x != null.
Testing:
You have been provided with a file containing 2 JUNIT test cases, and a testing
script. You must ensure that your code runs with these test cases and script on
the ECE Linux 64-bit machines, such as Kamek. Instructions for running the
script are provided separately.
More Instructions:
• You must use good style, including indentation, variable and method
names, spacing, and comments.
• You must ensure that your program compiles and runs with Java 8.
• You must complete the header.
• You must not delete or modify the package statement from the template
.java file.
• You must make sure that the test cases you are given pass with your
code, using JUNIT testing.
• When you are done, commit your SortTools.java file to Canvas.
• When done, check out all files to a clean directory, and compile and run
it on the Linux command line and in Eclipse/other IDE.
