How to implement Selection Sort using comparators for integers?

Question

I have been trying to implement the Selection Sort program in Java using comparators.

However, while the program works properly for Strings, it fails for integers and mixed case characters (haven't tried floating point values yet!)

Here is my code :

package edu.princeton.cs.algs4;

import java.util.Comparator;

public class Selection {

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

public static void sort(Object[] a, Comparator comparator) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (less(comparator, a[j], a[min])) min = j;
        }
        exch(a, i, min);
        assert isSorted(a, comparator, 0, i);
    }
    assert isSorted(a, comparator);
}

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

private static boolean less(Comparator comparator, Object v, Object w) 
{
    return comparator.compare(v, w) < 0;
}

private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

private static boolean isSorted(Comparable[] a) {
    return isSorted(a, 0, a.length - 1);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++)
        if (less(a[i], a[i-1])) return false;
    return true;
}

private static boolean isSorted(Object[] a, Comparator comparator) {
    return isSorted(a, comparator, 0, a.length - 1);
}

private static boolean isSorted(Object[] a, Comparator comparator, int 
lo, int hi) {
    for (int i = lo + 1; i <= hi; i++)
        if (less(comparator, a[i], a[i-1])) return false;
    return true;
}


private static void show(Comparable[] a) {
    for (int i = 0; i < a.length; i++) {
        StdOut.println(a[i]);
    }
}

public static void main(String[] args) {
    String[] a = StdIn.readAllStrings();
    Selection.sort(a);
    show(a);
    }
}

By the way, "StdIn" is the class provided by Princeton University for standard input and readAllStrings returns an array of all the strings read from file/standard input.

The above code worked perfectly for string data. However, when I wanted to test the same code for integer data, the compilation failed.

This is how I modified the code in the main() part:

public static void main() {
      Integer[] a = StdIn.readAllInts();
      Selection.sort(a);
      Selection.show(a);
}

readAllInts() is similar to readAllStrings(). It reads all integers and returns an array of integers.

However, upon compilation I got the following error:

int[] cannot be converted to Integer[]

Therefore i replaced the code again as follows :

public static void main(String[] args) {
       int[] a = StdIn.readAllInts();
       Selection.sort(a);
       Selection.show(a);
}

However, again I got errors:

Selection.java:80: error: method show in class Selection cannot be applied to given types; reason: argument mismatch; int cannot be converted to Comparable[]

and this error to:

Selection.java:79: error: no suitable method found for sort(int[])

Could anyone please tell me how do I go around this problem? I have found one method that works but there I need to initialise the integer array first and also provide the values.

Which means i cannot read from the file unlike the way I did for String.

Here are the links to the respective APIs for further reference :

Selection Sort

StdIn API

Thanks In Advance!!

Answer 1

You've got a classic "impedence mismatch" situation here:

• StdIn.readAllInts() gives you an int[]
• Selection.sort() and Selection.show() prefer Integer[]

Short of rewriting StdIn.readAllInts per Mike's suggestion, there's no magic solution. You'll need to take the int[] you get from StdIn.readAllInts(), create an Integer[] of the the same length, and copy the numbers from the int[] to the Integer[] one-by-one using a loop.