In JAVA Please Summary Implement a O(n * log(n)) algorithm of your choice that s
ID: 3750588 • Letter: I
Question
In JAVA Please
Summary
Implement a O(n * log(n)) algorithm of your choice that sorts arrays of objects that extend the Comparable<T> interface.
The Comparable<T> interface
The Comparable<T> 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:
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<T> interface)
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<T> 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:
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.
For testing purposes, you could call this method with any type that extends the Comparable<T> interface. For example:
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
Explanation / Answer
/**
* Example 116 - A Generic Quicksort Method for Comparable Values
*/
public class Sort {
public static <T extends Comparable<T>> void qsort(T[] arr, int a, int b) {
if (a < b) {
int i = a, j = b;
T x = arr[(i + j) / 2];
do {
while (arr[i].compareTo(x) < 0)
i++;
while (x.compareTo(arr[j]) < 0)
j--;
if (i <= j) {
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
} while (i <= j);
qsort(arr, a, j);
qsort(arr, i, b);
}
}
/*
* This function takes last element as pivot, places the pivot element at its
* correct position in sorted array, and places all smaller (smaller than pivot)
* to left of pivot and all greater elements to right of pivot
*/
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/*
* The main function that implements QuickSort() arr[] --> Array to be sorted,
* low --> Starting index, high --> Ending index
*/
void sort(int arr[], int low, int high) {
if (low < high) {
/*
* pi is partitioning index, arr[pi] is now at right place
*/
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
Integer[] ia = { 30, 20, 10, 5, 6, 99 };
Sort.<Integer>qsort(ia, 0, ia.length - 1);
for (Integer i : ia) {
System.out.println(i);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.