How can I properly using Comparables in this situation?

161
February 09, 2021, at 8:10 PM

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?

Rent Charter Buses Company