Sorting algorithms - How to discover comparisons and drives

Question

    package faculdade;

import java.util.Random;

public class Ordenacao {

    public static long comparacao;

    public static long movimentacao;

    public static void main(String[] args) {
        int[] vetor = new int[1000];
        fill(vetor);
        System.out.println("Vetor criado:");
        // show(vetor);
        // tempo inicial
        long tempoInicial = System.currentTimeMillis();
        //selectionSort(vetor);
        bubbleSort(vetor);
        //insertionSort(vetor);
        //quickSort(vetor, 0, vetor.length - 1);
        // tempo final
        long tempoFinal = System.currentTimeMillis();

        System.out.println("Executado em = " + (tempoFinal - tempoInicial) + " ms");
        System.out.println("\n Comparações: " + comparacao + " Movimentaçoes: " + movimentacao);
        System.out.println("Finalizado.");


    }

    public static void selectionSort(int[] vetor) {
        comparacao = 0;
        movimentacao = 0;
        for (int i = 0; i < vetor.length - 1; i++) {
            int menor = i;
            for (int j = i + 1; j < vetor.length; j++) {
                comparacao++;
                if (vetor[j] < vetor[menor]) {
                    comparacao++;
                    menor = j;
                }

            }
            swap(vetor, i, menor);
            // show(vetor);
            movimentacao++;
        }
    }

    public static void bubbleSort(int[] vetor) {
        movimentacao = 0;
        comparacao = 0;
        for (int i = vetor.length; i >= 1; i--) {
            for (int j = 1; j < i; j++) {
                if (vetor[j - 1] > vetor[j]) {
                    swap(vetor, j, j-1);
                    comparacao++;
                }
            }
            show(vetor);
        }
    }

    public static void insertionSort(int[] vetor) {
        comparacao = 0;
        movimentacao = 0;
        for (int i = 1; i < vetor.length; i++) {
            int current = vetor[i];
            int j = i - 1;
            while (j >= 0 && current < vetor[j]) {
                vetor[j + 1] = vetor[j];
                j--;
                comparacao++;
            }
            // at this point we've exited, so j is either -1
            // or it's at the first element where current >= a[j]
            vetor[j + 1] = current;
        }

            show(vetor);
            movimentacao++;
    }

    public static void quickSort(int vetor[], int esquerda, int direita) {

        int esq = esquerda;
        int dir = direita;
        int pivo = vetor[(esq + dir) / 2];
        int troca;

        while (esq <= dir) {
            while (vetor[esq] < pivo) {
                esq = esq + 1;

            }
            while (vetor[dir] > pivo) {
                dir = dir - 1;

            }
            if (esq <= dir) {
                troca = vetor[esq];
                vetor[esq] = vetor[dir];
                vetor[dir] = troca;
                esq = esq + 1;
                dir = dir - 1;
                movimentacao++;

            }
            comparacao++;
        }
        if (dir > esquerda) {
            quickSort(vetor, esquerda, dir);

        }

        if (esq < direita) {
            quickSort(vetor, esq, direita);

        }


    }

    public static void fill(int[] vetor) {
        Random r = new Random();
        for (int i = 0; i < vetor.length; i++) {
            vetor[i] = r.nextInt(100);
        }
    }

    public static void show(int[] vetor) {
        for (int i = 0; i < vetor.length; i++) {
            System.out.print(vetor[i] + " ");
        }
        System.out.println("");
    }

    public static void swap(int[] vetor, int a, int b) {
        int aux = vetor[a];
        vetor[a] = vetor[b];
        vetor[b] = aux;
        movimentacao++;

    }

}

At the time of executing, the comparison number is being equal to the drive number. I believe it is wrong

Answer 1

The numbers of comparison and movement are always the same because you only add it when you enter the if. If vetor[j - 1] is greater than vetor[j] it does not enter the if, so it does not add in the variable comparacao, but the comparison was made.

Your method should be like this:

public static void bubbleSort(int[] vetor) {
    movimentacao = 0;
    comparacao = 0;
    for (int i = vetor.length; i >= 1; i--) {
        for (int j = 1; j < i; j++) {
            comparacao++;
            if (vetor[j - 1] > vetor[j]) {
                swap(vetor, j, j-1);
            }
        }
        show(vetor);
    }
}