I'm doing an exercise from Sedgewick's Algorithms textbook, the exercise is to find the number of compares for quicksort. Below is my code:
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import java.util.Random;
public class quickSortCompareCheck {
private static int numberOfCompares;
private static Comparable[] generateArray(int n) {
Random random = new Random();
Comparable[] arr = new Comparable[n];
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt();
}
return arr;
}
private static class QuickSort {
private static void quickSort(Comparable[] arr) {
StdRandom.shuffle(arr);
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(Comparable[] arr, int lo, int hi) {
if (lo >= hi) return;
int partition = partition(arr, lo, hi);
quickSort(arr, lo, partition - 1);
quickSort(arr, partition + 1, hi);
}
private static int partition(Comparable[] arr, int lo, int hi) {
Comparable pivot = arr[lo];
int i = lo;
int j = hi + 1;
while (true) {
numberOfCompares++;
while (less(arr[++i], pivot)) {
if (i == hi) break;
numberOfCompares++;
}
numberOfCompares++;
while(less(pivot, arr[--j])) {
if (j == lo) break;
numberOfCompares++;
}
if (i >= j) break;
exchange(arr, i, j);
}
exchange(arr, lo, j);
return j;
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public static void main(String[] args) {
int[] sizes = {100,1000,10000};
for (int i = 0; i < sizes.length; i++) {
int size = sizes[i];
double exp = 2 * size * Math.log(size);
Comparable[] arr = generateArray(sizes[i]);
QuickSort.quickSort(arr);
StdOut.println("Expected compares is: " + exp);
StdOut.println("Actual compares is: " + numberOfCompares);
numberOfCompares = 0;
}
}
}
I'm getting the following errors:
quickSortCompareCheck.java:10: warning: [rawtypes] found raw type: Comparable
private static Comparable[] generateArray(int n) {
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:12: warning: [rawtypes] found raw type: Comparable
Comparable[] arr = new Comparable[n];
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:12: warning: [rawtypes] found raw type: Comparable
Comparable[] arr = new Comparable[n];
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:21: warning: [rawtypes] found raw type: Comparable
private static void quickSort(Comparable[] arr) {
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:26: warning: [rawtypes] found raw type: Comparable
private static void quickSort(Comparable[] arr, int lo, int hi) {
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:33: warning: [rawtypes] found raw type: Comparable
private static int partition(Comparable[] arr, int lo, int hi) {
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:34: warning: [rawtypes] found raw type: Comparable
Comparable pivot = arr[lo];
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:59: warning: [rawtypes] found raw type: Comparable
private static boolean less(Comparable v, Comparable w) {
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:59: warning: [rawtypes] found raw type: Comparable
private static boolean less(Comparable v, Comparable w) {
^
missing type arguments for generic class Comparable<T>
where T is a type-variable:
T extends Object declared in interface Comparable
quickSortCompareCheck.java:60: warning: [unchecked] unchecked call to compareTo(T) as a member of the raw type Comparable
return v.compareTo(w) < 0;
^
where T is a type-variable:
T extends Object declared in interface Comparable
10 warnings
I'm pretty new to Java and I'm not sure how to fix the code, I got it to work using the Integer class instead of Comparable since Integer implements Comparable, but I'd like to get my code working as it is. There's a solution (https://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/chapter2/section3/Exercise6.java) to the exercise that is similar to mine but the person generates the random array differently. Can someone please school me on how to fix this?
