In JAVA Please

Summary

Implement a O(n * log(n)) algorithm of your choice that sorts arrays of objects that extend the Comparable interface.

The Comparable interface

The Comparable interface is an interface that is built into the Java language and is used to represent objects of types that can be put in an order (for example, Strings, Integers, Doubles, etc). It is defined as follows:

public interface Comparable { public int compareTo(T other); } 

The method compareTo returns:

a negative number if "this" is considered to be less than "other"

0 if "this" is considered to be equal to "other"

a positive number if "this" is considered to be greater than "other"

For example, the following program would print "-1, 0, 1" (note that Integer extends the Comparable interface)

Integer a = 4; Integer b = 3; System.out.println(b.compareTo(a) + ", " + a.compareTo(a) + ", " + a.compareTo(b)); 

Generics

The comparable interface is an example of Java's generics feature. We haven't covered generics, but basically it means that the T in Comparable can represent whatever type we want. The exact details of how this works are beyond the scope of this lab (and probably beyond the scope of this class). But for now, just trust that it works. There are some special bits of syntax that you need to use in order to get generic classes to compile, but as long as you don't change the method signature from what is specified in the requirements section, you should be fine.

Inside the sort method, you can use the letter T as if it were the name of whatever type was currently being sorted.

Requirements

Your solution should be in a file called "Sort.java" which contains a method called sort defined as follows:

public class Sort { /** * Method to sort an array of comparable objects. Don't worry too much about this complicated method signature, * it is just some fancy syntax that means it can take an array of any comparable type and that it returns an array of * that same type */ public static > T[] sort(T[] inputArray) { //Student code here } } 

Whether the code sorts the original array or whether it returns a sorted copy of the original array is up to the student.

You may choose any O(n*log(n)) algorithm that you wish (most likely either merge sort or quick sort) to implement. The only thing you may not do is use any built-in java sorting algorithms.

Example code

Since we've never used any generics before, here is a very basic example of an implementation. In this simplistic example, the solution can only sort arrays of size 2.

public class Sort { public static > T[] sort(T[] array) { if(array.length != 2) { System.out.println("Uh oh! We don't know how to handle this in this silly example"); return null; } if(array[0].compareTo(array[1]) > 0) { T temp = array[1]; array[1] = array[0]; array[0] = temp; } return array; } } 

For testing purposes, you could call this method with any type that extends the Comparable interface. For example:

String[] strings = {"hello", "World", "how", "are", "you", "today"}; String[] sortedStrings = Sort.sort(strings); 

Evaluation

The evaluation of the sorting algorithms will be based on unit tests. In order to assert that the sorting algorithm is in fact O(n * log(n)), there will be one test that operates on a fairly large array and checks that the number of comparison operations performed is less than n * log(n) times some reasonable factor. If you believe that your algorithm is in fact within O(n*log(n)) and it does not pass that test, please email me with your justification of why you believe your algorithm is O(n * log(n)) and explain why you are performing more comparisons than expected.

Cannot use the Arrays.sort() function