0

I'm trying to figure out in the code below how to count the number of comparisons that are made, is there a way to do this in code?

Also in the for loop how come it iterates up to a.length - 1 and not a.length

public static void minmax1(int[] a) {

    if (a == null || a.length < 1)
        return;

    int min, max;

    // if only one element
    if (a.length == 1) {
        max = a[0];
        min = a[0];
        System.out.println("min: " + min + "\nmax: " + max);
        return;
    }

    if (a[0] > a[1]) {
        max = a[0];
        min = a[1];
    } else {
        max = a[1];
        min = a[0];
    }

    for (int i = 2; i <= a.length - 1; i++) {
        if (max < a[i]) {
            max = a[i];
        } else if (min > a[i]) {
            min = a[i];
        }
    }

    System.out.println("min: " + min + "\nmax: " + max);
}
netleap tom
  • 143
  • 4
  • 10
  • 1
    `i <= a.length - 1` == `i < a.length` (if `i` is an integer, at least). – Bernhard Barker Mar 02 '18 at 18:25
  • Your array is 0-based (first element is accessed at 0th index), so you can go upto `a.length - 1` index only. – Vasan Mar 02 '18 at 18:29
  • If you're looking to show that this code has at most some number of comparisons for any input (which you didn't exactly clearly indicate), you'll need to argue about all the things that can happen at every step in the code, and how this would affect other steps. Your loop has 2 comparisons, so the only way the code can have less than 2n comparisons is if you can somehow prove that it's impossible to hit both comparison for every element. What value does an element need to have for both comparisons to happen? Can you make an array where each element has such a value? – Bernhard Barker Mar 02 '18 at 18:32
  • [Algorithm to find high/low numbers with at most 1.5n comparisons](https://stackoverflow.com/q/9007993). [How to find max. and min. in array using minimum comparisons?](https://stackoverflow.com/q/13544476) – Bernhard Barker Mar 02 '18 at 18:39

1 Answers1

-1

how to count the number of comparisons that are made?

You add a counter variable, then increment it every time you make a value comparison, like this:

public static void minmax1(int[] a) {

    if (a == null || a.length < 1)
        return;

    int min, max, count = 0;                       // added comparison counter

    // if only one element
    if (a.length == 1) {
        max = a[0];
        min = a[0];
        System.out.println("min: " + min + "\nmax: " + max);
        return;
    }

    count++;                                       // comparison on next line
    if (a[0] > a[1]) {
        max = a[0];
        min = a[1];
    } else {
        max = a[1];
        min = a[0];
    }

    for (int i = 2; i <= a.length - 1; i++) {
        if (max < a[i]) {
            count++;                               // 1 comparison to get here
            max = a[i];
        } else if (min > a[i]) {
            count += 2;                            // 2 comparisons to get here
            min = a[i];
        } else {
            count += 2;                            // 2 comparisons to get here
        }
    }

    System.out.println("min: " + min + "\nmax: " + max);
    System.out.println("comparisons: " + count);   // print comparison counter
}
Andreas
  • 154,647
  • 11
  • 152
  • 247
  • A comparison counter can only tell you what happens in relatively small set of manually generated (or at least manually decided upon) inputs, not what would be true for all inputs (which I'm assuming is what the question is asking about, especially consider the similarity between this question and [Algorithm to find high/low numbers with at most 1.5n comparisons](https://stackoverflow.com/q/9007993)). – Bernhard Barker Mar 02 '18 at 18:41
  • @Dukeling Read the first paragraph of the question again. It specifically asks if there is a way to do the counting in the code. I read the question as OP asking for empirical evidence of actual comparison count using actual data vs. a theoretical comparison count like you're referring to. --- For the code in the question, best case (values in ascending order) is a comparison count of `n - 1` and worst case (values in descending order) is `2n - 3`, with typical comparison count being somewhere in between, though likely somewhere above `1.5n`, because most values will be between `min` and `max` – Andreas Mar 02 '18 at 19:13