## 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.