Análise de algoritmo em Java

Programação Java
#1

Olá,

Eu gostaria que alguém me ajudasse a analisar um algoritmo em Java. Vejamos:

import java.util.Arrays;


public class Sort {
	
	
	public static void main(String args[])
	{
		
		int[] a = {10,12,1,5,30};
		
		int i, j = 0;
		
		
		for (j = 2; j < a.length; j++)
		{
			int key = a[j];
			System.out.println("key: " + key);
			
			System.out.println("j: " + j);
			i = j - 1;
			System.out.println("i = j - 1: " + i);
			
			
			System.out.println(i);
			while(i >= 0 && a[i] > key) {
				a[i + 1] = a[i];
				i = i - 1;
			}			
			
			a[i + 1] = key;
	
		}
		
		for (j = 0; j < a.length; j++) {
			System.out.println(Arrays.toString(a));
			
		}
		
	}


}

Porque entra no loop (while), sendo que a[i] não é maior que key ?

Agradeço!

#2

Amigo, na primeira vez que roda o algorítimo, o i vale 1
logo a[i] é igual a 12
e key ta valendo a[j] (ou seja 1)

entao ele entra no while.

#3

E aew hackum td blz?

Na primeira passada vc tem i > 0 ( i == 1) e a[i] é maior que a key ( a[1] == 12 e key == 1 ). É justamente o que precisa para entrar no while.

#4

[quote=hackum]Olá,

Eu gostaria que alguém me ajudasse a analisar um algoritmo em Java. Vejamos:

import java.util.Arrays;


public class Sort {
	
	
	public static void main(String args[])
	{
		
		int[] a = {10,12,1,5,30};
		
		int i, j = 0;
		
		
		for (j = 2; j < a.length; j++)
		{
			int key = a[j];
			System.out.println("key: " + key);
			
			System.out.println("j: " + j);
			i = j - 1;
			System.out.println("i = j - 1: " + i);
			
			
			System.out.println(i);
			while(i >= 0 && a[i] > key) {
				a[i + 1] = a[i];
				i = i - 1;
			}			
			
			a[i + 1] = key;
	
		}
		
		for (j = 0; j < a.length; j++) {
			System.out.println(Arrays.toString(a));
			
		}
		
	}


}

Porque entra no loop (while), sendo que a[i] não é maior que key ?

Agradeço![/quote]

Porque quando j=2 e quando j=3, i sera maior que o e a[i] sera maior que key

vou postar o codigo acrescido de algumas linhas para te ajudar a visualizar :

import java.util.Arrays;


public class Sort {


    public static void main(String args[])
    {

        int[] a = {10,12,1,5,30};
        int i, j = 0;

        for (j = 2; j < a.length; j++)
        {
            int key = a[j];
            System.out.println("key: " + key);

            System.out.println("j: " + j);
            i = j - 1;
            System.out.println("i = j - 1: " + i);
            System.out.println(i);
// Acrescentei-------------------------------------------------------------------------------
            System.out.println("VERIFICAÇÃO PARA j="+j);
            System.out.print("i:"+ i);
            System.out.print("         a[i]: "+a[i]);//
            System.out.print("          key: "+ key);//
            System.out.println("       ((i >= 0)&&(a[i] > key)): ");//
            System.out.println("------------------------------");
//--------------------------------------------------------------------------------------------
            
                        while((i >= 0)&&(a[i] > key))
                        {  a[i + 1] = a[i];
                           i = i - 1;
                        }
                        
            
            
            a[i + 1] = key;

        }
//Porque entra no loop (while), sendo que a[i] não é maior que key ?
       for (j = 0; j < a.length; j++)
                        {System.out.println(Arrays.toString(a));
                        }

    }
}

saida do codigo que postei:

run:
key: 1
j: 2
i = j - 1: 1
1
VERIFICAÇÃO PARA j=2
i:1         a[i]: 12          key: 1       ((i >= 0)&&(a[i] > key)): 
------------------------------
key: 5
j: 3
i = j - 1: 2
2
VERIFICAÇÃO PARA j=3
i:2         a[i]: 12          key: 5       ((i >= 0)&&(a[i] > key)): 
------------------------------
key: 30
j: 4
i = j - 1: 3
3
VERIFICAÇÃO PARA j=4
i:3         a[i]: 12          key: 30       ((i >= 0)&&(a[i] > key)): 
------------------------------
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
CONSTRUÍDO COM SUCESSO (tempo total: 0 segundos)
#5

Em primeira instância, eu gostaria de agradecer a todos que me responderam. Porém, eu ainda não compreendi. Vejam bem:

i:3         a[i]: 12          key: 30       ((i >= 0)&&(a[i] > key)):

a[i] não é maior que key. Então porque entrou no loop ? Estamos dizendo na última verificação, que é no caso a matriz, posição 4.

#6

[quote=hackum]Em primeira instância, eu gostaria de agradecer a todos que me responderam. Porém, eu ainda não compreendi. Vejam bem:

i:3         a[i]: 12          key: 30       ((i >= 0)&&(a[i] > key)):

a[i] não é maior que key. Então porque entrou no loop ? Estamos dizendo na última verificação, que é no caso a matriz, posição 4.[/quote]

Na verdade vc não esta entendendo porque a impressao ocorre depois … mudei o código coloquei a impressaõ dentro do proprio laço for da em cima…agora é mais facil entender…
segue o código:[code]
import java.util.Arrays;

public class Sort {

public static void main(String args[])
{
    // Acrescentei-------------------------------------------------------------------------------
    int impressao = 1;
    // -------------------------------------------------------------------------------

    int[] a = {10,12,1,5,30};
    int i, j = 0;

    for (j = 2; j < a.length; j++)
    {
        // Acrescentei-------------------------------------------------------------------------------
        impressao = 1;
        int laco ;
        
        laco = j-1;
        System.out.println("--Execução do Laço nº:---"+ laco);
        //-------------------------------------------------------------------------------
        int key = a[j];
        System.out.println("key: " + key);

        System.out.println("j: " + j);
        i = j - 1;
        System.out.println("i = j - 1: " + i);
        System.out.println(i);

// Acrescentei-------------------------------------------------------------------------------
System.out.println(“VERIFICAÇÃO PARA j=”+j);
System.out.print(“i:”+ i);
System.out.print(" a[i]: “+a[i]);//
System.out.print(” key: “+ key);//
System.out.println(” ((i >= 0)&&(a[i] > key)): “);//
// System.out.println(”------------------------------");

                    if((i >= 0)&&(a[i] > key)){
                     System.out.println(" Havera Impressao, pois ((i >= 0)&&(a[i] > key))");
                    }
                    else
                    {
                     System.out.println(" Não Havera Impressao, pois esta condição é falsa((i >= 0)&&(a[i] > key))");
                    }

//--------------------------------------------------------------------------------------------
while((i >= 0)&&(a[i] > key))
{ a[i + 1] = a[i];
i = i - 1;
// Acrescentei-------------------------------------------------------------------------------
impressao = 0;
// -------------------------------------------------------------------------------
}
// Acrescentei-------------------------------------------------------------------------------
if(impressao == 0) {
for (int h = 0; h < a.length; h ++)
{System.out.println(Arrays.toString(a));
}
}
// -------------------------------------------------------------------------------

         System.out.println("------------------------------");
        a[i + 1] = key;

    }

//Porque entra no loop (while), sendo que a[i] não é maior que key ?
// for (j = 0; j < a.length; j++)
// {System.out.println(Arrays.toString(a));
// }

}

}
[/code]

segue abaixo a saida deste código:[code]
debug:
–Execução do Laço nº:—1
key: 1
j: 2
i = j - 1: 1
1
VERIFICAÇÃO PARA j=2
i:1 a[i]: 12 key: 1 ((i >= 0)&&(a[i] > key)):
Havera Impressao, pois ((i >= 0)&&(a[i] > key))
[10, 10, 12, 5, 30]
[10, 10, 12, 5, 30]
[10, 10, 12, 5, 30]
[10, 10, 12, 5, 30]
[10, 10, 12, 5, 30]

–Execução do Laço nº:—2
key: 5
j: 3
i = j - 1: 2
2
VERIFICAÇÃO PARA j=3
i:2 a[i]: 12 key: 5 ((i >= 0)&&(a[i] > key)):
Havera Impressao, pois ((i >= 0)&&(a[i] > key))
[1, 10, 10, 12, 30]
[1, 10, 10, 12, 30]
[1, 10, 10, 12, 30]
[1, 10, 10, 12, 30]
[1, 10, 10, 12, 30]

–Execução do Laço nº:—3
key: 30
j: 4
i = j - 1: 3
3
VERIFICAÇÃO PARA j=4
i:3 a[i]: 12 key: 30 ((i >= 0)&&(a[i] > key)):
Não Havera Impressao, pois esta condição é falsa((i >= 0)&&(a[i] > key))

CONSTRUÍDO COM SUCESSO (tempo total: 0 segundos)
[/code]

Qualquer dúvida estou a disposição!!!

#7

Use o debug e você saberá o que está acontecendo exatamente

#8

O que ocorre nessa parte do código ? (Dentro do while).

a[i + 1] = a[i];
#9

[quote=hackum]O que ocorre nessa parte do código ? (Dentro do while).

a[i + 1] = a[i];

Nessa parte de código, você coloca na posição (i+1) do array, o que tem na posição i.

Seria o equivalente a executar isso:

int valorDoIndiceI = a[i];
a[i+1] = valorDoIndiceI

exemplo para um array com os valores {1,5,7}

Para i = 0, o código faz o array ficar {1,1,5}

int valorDoIndiceZero = a[0];
a[1] = valorDoIndiceZero;
#10

Estou conseguindo entender a lógica.

#11

hackum, já abriu esse código em modo de debug em qualquer IDE que seja? Faça isso por favor.

Outra dica que dou é mudar o nome das variáveis, i para indiceDoMenorElemento, ou indiceDoElementoQueSeráMovido. Deixar as coisas por extenso vai clarear a tua mente que deve estar viciada tentando seguir uma lógica que não está escrita. Tente falar em voz alta um código escrito por extenso.

#12

Agora sim, estou conseguindo entender. Porém, há uma parte que está errada, em meu ponto de vista, veja:

import java.util.Arrays;


public class SortChanged {


    public static void main(String args[])
    {

    	int[] a = {10,12,1,5,30};
        int i, j = 0;

        for (j = 2; j < a.length; j++)
        {
            int key = a[j];
            i = j - 1;
            System.out.println("i = " + i + ", a[i] = " + a[i] + ", key = " + key);  
            
                        while((i >= 0)&&(a[i] > key))
                        {  
                        	a[i + 1] = a[i];
                            i = i - 1;
                            System.out.println("Within of the While " + Arrays.toString(a));
    
                        }
                        
            
            
            a[i + 1] = key;
            System.out.println("Out of the while: " + Arrays.toString(a));

        }
        
       for (j = 0; j < a.length; j++)
       {
    	   System.out.println(Arrays.toString(a));
       }
                        
    }
}



Output:

i = 1, a[i] = 12, key = 1
Within of the While [10, 12, 12, 5, 30]
Within of the While [10, 10, 12, 5, 30]
Out of the while: [1, 10, 12, 5, 30]
i = 2, a[i] = 12, key = 5
Within of the While [1, 10, 12, 12, 30]
Within of the While [1, 10, 10, 12, 30]
Out of the while: [1, 5, 10, 12, 30]
i = 3, a[i] = 12, key = 30
Out of the while: [1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]
[1, 5, 10, 12, 30]

Na linha 49: Out of the while: [1, 10, 12, 5, 30]. O correto não seria exibir, [10,1,12,5,30] ?

#13