2

Tenho um trabalho da faculdade em que devo criar alguns vetores com números aleatórios e em seguida ordenar em alguns métodos(insertion,bubble,merge,etc).

Depois de ordenar, preciso contar o número de comparações que cada método fez. Como posso fazer essa contagem em cada método?

Esse algoritmo abaixo está organizando 2 vetores, um com tamanho 5, gerando 5 números aleatórios e outro com tamanho 10, gerando 10 números aleatórios. É possível contar o número total de comparações que foi feita?

Meu código de InsertionSort atualmente, funciona normalmente mas a contagem de comparações está incorreta:

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;
    }
}
3
  • Está vendo esse if no método estático? Só botar um comparacoes++ antes dele, sendo static int comparacoes uma variável estática inteira; obviamente, resete o contator de comparações antes de cada rodada... Commented 19/11/2018 às 19:59
  • @JeffersonQuesado mas desse jeito seria possível ter o número de comparações de cada vetor(o de 5 e de 10)? Por que pelo o que entendi só contaria pra 1
    – ncesar
    Commented 19/11/2018 às 20:08
  • se você por no canto correto, o incremento ocorrerá junto da comparação, então estará fazendo no canto correto. Verificará que é proporcional ao quadrado do tamanho do vetor Commented 19/11/2018 às 20:13

1 Resposta 1

0

A resposta é simples. Está no seu for.

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

Vc faz um for, que vai até N (n sendo o tamanho do vetor). Dentro dele, temos outro for que vai até no máximo N - 1 (na verdade de N -1 para 0). Isso implica em uma complexidade de N * N - N, ou N-ao-quadrado. (para efeitos de complexidade, pegamos o maior expoente)

Veja, isso parece meio simplista. Vc pode ver que no melhor caso ele faz apenas n comparações, mas no pior caso, em que tudo está bagunçado, ele vai ser n-quadrado.

Eu podia fazer os cálculos com vc para exemplificar: Com N=5, o primeiro loop faz 5 vezes.

  • Na primeira vez, ele faz 1 vez.
  • Na segunda passagem, ele faz 2 comparações,
  • Na terceira, ele fez 3 comparações,
  • Na Quarta, ele faz 4 comparações,
  • E na quinta ele faz 5.

Somando, 1 + 2 + 3 + 4 + 5 = 15 vezes. Pode parecer longe de 25 que seria N-ao-quadrado, mas é próximo de 20, que seria n-ao-quadrado menos N.

Quando falamos de complexidade computacional saber se ela é N-ao-quadrado, se ela é N, ou log N, é mais importante do que ter o número certo de vezes, porque para cada uma dessas categorias, temos um grupo de algorítimos que lidam com ela.

1
  • Obrigado Alexei!!
    – ncesar
    Commented 21/11/2018 às 21:40

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .