The goals of this assignment are:
WARNING: In this assignment you are NOT ALLOWED to import any packages. For example, you cannot use the builtin
Arrays
java class to print out an array. Doing so will result in earning ZERO POINTS for a method that uses it.
IF YOUR CODE DOES NOT COMPILE, YOU WILL EARN 0 POINTS FROM THE AUTOGRADER.
In this last assignment, you will implement two classes: SuperDuperArray
and SuperDuperSortedArray
. These classes will implement the interface called SuperArray
. We will provide you the interface called SuperArray
that we provide.
You can find the interface here.
Both classes will keep track of an array of String
s.
For both of these classes, the toString()
method should return one line that contains all the Strings. Each item should be seperated by a space.
For remove
, it should return a boolean indicating if the input element exists in the array or not.
SuperDuperArray
will be a wrapper around a String[]
. Create a String[]
as a private instance variable of your class.
Implement a value constructor which takes one argument: int capacity
. This will be the size of your array. Initialize your array instance variable in the constructor accordingly.
In addition to implementing all methods in the interface, SuperDuperArray
, the class must include the following:
String[] sort(int order)
that takes in an integer to determine whether to sort in ascending
or descending
order. 1
means ascending
and 2
means descending
. The sort
method must return a new sorted array. You are free to use Bubble or Selection Sort. You can use the built-in String methods for determining whether one String is greater than another.Next, implement a class SuperDuperSortedArray
which also implements the interface SuperArray
. In this class, the array of elements must always be sorted. Each time an element is added, make sure the list stays sorted. One approach would be to add the element and then sort the elements. However, this approach would be O(n^2)
. For full points, come up with a faster approach.
Think about how you can implement remove
and contains
differently to be more efficient than in SuperDuperArray
. For full points, add
and remove
should have a worst case complexity of O(n)
and contains
should have a worst case complexity of O(logn)
.
This class should also have a value constructor which takes a capacity.
In a text file called README.txt
answer the following questions:
Vet
. Which class would you rather use SuperDuperSortedArray
or SuperDuperSorted
? Make sure to justify your answer - there is no wrong answer here.SuperDuperArray
and SuperDuperSortedArray
: size
, isEmpty
, add
, remove
, contains
, toString
. For SuperDuperArray
, list the Big O notation of sort
.Submit the following files to the assignment called HW11
on Gradescope:
SuperDuperArray.java
SuperDuperSortedArray.java
README.txt
Make sure to name these files exactly what we specify here and name the methods exactly what we specify too. Otherwise, our autograders might not work and we might have to take points off.