CODEWITHSUNDEEP
javasortingcomparatortimsort
Animesh Pandey
Animesh Pandey

Reputation: 6018

How to count the number of comparisons in a Comparator/Comparable?

Suppose I have the following compareTo:

public int compareTo(RandomClass o) {
    if (this.value() < o.value()) {
        return -1;
    } else if (this.value() > o.value()) {
        return 1;
    } else {
        return 0;
    }
}

I want to know the exact number of comparisons when I call Arrays.sort(randomClassArray), where randomClassArray has 100 objects?

Upvotes: 1

Views: 2116

Answers (6)

user4910279
user4910279

Reputation:

Try this.

public class ComparatorCounter<T extends Comparable<T>> implements Comparator<T> {

    public int counter = 0;

    @Override
    public int compare(T o1, T o2) {
        ++counter;
        return o1.compareTo(o2);
    }
}

and

RandomClass[] array = new RandomClass[9];
// fill array
ComparatorCounter<RandomClass> comp = new ComparatorCounter<>();
Arrays.sort(array, comp);
System.out.println("compare count=" + comp.counter);

Upvotes: 0

nstosic
nstosic

Reputation: 2614

You could write your own class implementing Comparator<RandomClass> interface:

public class CustomComparator implements Comparator<RandomClass> {

    private final AtomicInteger counter;

    public CustomComparator() {
        this.counter = new AtomicInteger(0);
    }

    @Override
    public int compare(RandomClass val1, RandomClass val2) {
        this.counter.incrementAndGet();
        if (val1.value() < val2.value()) {
            return -1;
        } else if (val1.value() > val2.value()) {
            return 1;
        }
        return 0;
    }

    public int getNumberOfOperations() {
        return this.counter.intValue();
    }
}

Then call static <T> void sort(T[] a, Comparator<? super T> c) function with the following arguments:

CustomComparator comparator = new CustomComparator();
Arrays.sort(randomClassAray, comparator);
System.out.println("Number of operations = " + String.valueOf(comparator.getNumberOfOperations()));

Upvotes: 0

Nicolas Filotto
Nicolas Filotto

Reputation: 45005

For me the best approach is to use a decorator of type Comparator that will count the total of times it is called something like:

public class Counter<T> implements Comparator<T> {

    private final AtomicInteger counter;
    private final Comparator<T> comparator;

    public Counter(Comparator<T> comparator) {
        this.counter = new AtomicInteger();
        this.comparator = comparator;
    }

    @Override
    public int compare(final T o1, final T o2) {
        counter.incrementAndGet();
        return comparator.compare(o1, o2);
    }

    public int getTotalCalled() {
        return this.counter.get();
    }
}

Then you will provide your own comparator to it and use Arrays.sort(T[], Comparartor) to sort your array, as next:

Counter<SomeClass> counter = new Counter<>(myComparator);
Arrays.sort(randomClassArray, counter);
int totalCalled = counter.getTotalCalled();

Upvotes: 2

Darwin.Lau
Darwin.Lau

Reputation: 226

Set a global counter. Below is my code:

public class ComparatorCount {

static int counter = 0;

public static void main(String[] args) {
    Random random = new Random();
    List<RandomClass> randomClassList = new ArrayList<>();
    for(int i = 0 ; i < 100 ; i++) {
        RandomClass rc = new RandomClass();
        rc.setValue(i + random.nextInt(100));
        randomClassList.add(rc);
    }

    Collections.sort(randomClassList);

    randomClassList.forEach(x -> System.out.println(x));

    System.out.println("compare " + counter + " times in total.");
}

static class RandomClass implements Comparable<RandomClass> {

    private int value;

    public int value() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public String toString() {
        return "randomClass : " + value;
    }

    @Override
    public int compareTo(RandomClass o) {
        counter++;
        if (this.value() < o.value()) {
            return -1;
        } else if (this.value() > o.value()) {
            return 1;
        } else {
            return 0;
        }
    }
}

}

Upvotes: 0

pushpavanthar
pushpavanthar

Reputation: 869

declare a public static int variable and increment it in the compareTo() method. After Arrays.sort(randomClassArray) print the variable and reset it.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234825

Consider binding an atomic integral type field called counter, say to your collection. Set it to zero before your sorting algorithm, then increment it by one (atomically) inside compareTo.

It needs to be atomic in case your sorting algorithm is parallelised. I'd shy away from making compareTo synchronized as that will probably ruin the benefit of any parallelisation.

Perhaps it needs to be incremented twice for the return values of 1, 0?

Upvotes: 0

Related Questions