How to count the number of comparisons of an algorithm (insertionSort)?

Question

I have a college job where I should create some vectors with random numbers and then sort in some methods(Insertion,Bubble,merge,etc).

After sorting, I need to count the number of comparisons that each method has made. How can I do this count in each method?

This algorithm below is organizing 2 vectors, one with size 5, generating 5 random numbers and another with size 10, generating 10 random numbers. It is possible to count the total number of comparisons made?

My Insertionsort code currently works normally but the comparison count is incorrect:

package insertion;

import java.util.Random;

public class insertion {
    public static void main(String a[]){
        Random r = new Random();//util para chamar os números aletórios

        int[] vet5 = new int[5];
        int[] vet10 = new int[10];

        //vet5 não ordenados
        for (int i = 0; i < vet5.length; i++) {
            vet5[i] = r.nextInt(5);
        }

        //vet10 não ordenados
        for (int i = 0; i < vet10.length; i++) {
            vet10[i] = r.nextInt(10);
        }

        //--------------------------------------------//
        //vet5 ordenados
        int[] arr2 = doInsertionSort(vet5);
        int cont5 = 0;
        System.out.println("\nVetores com 5 ordenados: ");
        for(int i:arr2){
            System.out.print(i);
            System.out.print(", ");
            cont5++;
        }
        System.out.println("\nTotal de comparações com 5: "+cont5);

        //vet10 ordenados
        int[] arr3 = doInsertionSort(vet10);
        int cont10 = 0;
        System.out.println("\nVetores com 10 ordenados: ");
        for(int i:arr3){
            System.out.print(i);
            System.out.print(", ");
            cont10++;
        }
        System.out.println("\nTotal de comparações com 10: "+cont10);

    }

    public static int[] doInsertionSort(int[] input){

        int temp;
        for (int i = 1; i < input.length; i++) {
            for(int j = i ; j > 0 ; j--){
                if(input[j] < input[j-1]){
                    temp = input[j];
                    input[j] = input[j-1];
                    input[j-1] = temp;
                }
            }
        }
        return input;
    }
}

Answer 1

The answer is simple. It’s in your for.

  for (int i = 1; i < input.length; i++) {
            for(int j = i ; j > 0 ; j--){

Vc makes one for, which goes up to N (n being the size of the vector). Inside, we have another for that goes up to the maximum N - 1 (actually from N -1 to 0). This implies a complexity of N * N - N, or N-squared. (for complexity purposes, we take the larger exponent)

See, that sounds kind of simplistic. You can see that in the best case it makes only n comparisons, but in the worst case, in which everything is messy, it will be n-square.

I could do the calculations with you to illustrate: With N=5, the first loop makes 5 times.

• The first time, he does it once.
• In the second passage, he makes 2 comparisons,
• In the third, he made three comparisons,
• On Wednesday, he makes four comparisons,
• And on Thursday he turns 5.

Adding up, 1 + 2 + 3 + 4 + 5 = 15 times. It may seem far from 25 that it would be N-to-square, but it is close to 20, which would be n-to-square less N.

When we talk about computational complexity, whether it’s N-squared, whether it’s N, or log N, it’s more important than having the right number of times, because for each of these categories, we have a group of algorithms that deal with it.