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

2

I have a college job where I have to 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 each method made. How can I make this count in each method?

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

My InsertionSort code currently works normally but the compare 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;
    }
}
    
asked by anonymous 19.11.2018 / 20:54

1 answer

0

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

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

You make a for, that goes to N (n being the size of the vector). Inside it, we have another for that goes up to maximum N - 1 (actually from N -1 to 0). This implies a complexity of N * N - N, or N - to - square. (for the sake of complexity, we get the biggest exponent)

Look, this sounds kind of simplistic. You can see that in the best case he only makes n comparisons, but in the worst case, where everything is messed up, it will be n-square.

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

  • The first time, it does 1 time.
  • In the second pass, it makes 2 comparisons,
  • In the third, he made 3 comparisons,
  • In Fourth, it makes 4 comparisons,
  • And on the fifth it does 5.

Adding, 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 minus N. When we speak of computational complexity, whether it is N-to-square, whether it is N, or log N, is 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.

    
19.11.2018 / 22:15