Insertion Sort

O && representa o operador lógico AND. O segundo laço é executado enquanto j >= E array[j] > a. Ou seja, enquanto ambas as condições forem verdadeiras.

Apenas para acrescentar, o operador lógico && (condicional E) possui o comportamento conhecido como curto-circuito que determina que a segunda expressão booleana só será avaliada caso a primeira seja verdadeira. Isso é bastante útil porque, para uma expressão condicional E ser verdadeira os dois operandos precisam ser verdadeiros, logo, se o primeiro já é falso, não existe a necessidade de se avaliar o segundo.

Essa informação é importante porque, caso utilizasse um operador condicional E comum (&) nesse loop for, seria lançada uma exceção ArrayIndexOutOfBoundsException, pois, na primeira iteração j é igual a -1, conforme exemplificado abaixo: for (int i = 0; i < array.length; i++) { int a = array[i]; for (int j = i - 1; j >= 0 & array[j] > a; j--) { // loop for utilizando o operador Condicional E comum (bitwise) array[j + 1] = array[j]; array[j] = a; } }Na primeira iteração j vale -1. Como aqui não foi utilizado o E curto-circuito (&&), mesmo a primeira expressão sendo falsa (j>=0), a segunda expressão será avaliada (array[j]>a) que é o mesmo que array[-1]>a e índices negativos são sempre inválidos. O que iria gerar a exceção citada acima. Quando o && é utilizado isso não acontece porque ao avaliar que j>=0 é falso, a expressão array[j]>a não é avaliada, portanto, toda vez que j for menor que 0 a segunda expressão não é alcançada evitando que a exceção seja lançada.

Como funciona o Insertion Sort?

É uma técnica de ordenação muito simples, você divide o array em 2 partes:

-> A parte à esquerda do índice, essa parte está sempre ordenada
-> Do índice pra frente ainda não está.

Você vai correr todos os índices do array, um a um, e em cada um deles, vai trocar seu valor com todos os números à esquerda dele que são maiores. Exemplo:

int[] array = new int[]{5, 7, 1, 9};

i
7,   5,   1,   9

OK
     i
7,   5,   1,   9

OK
     i
5,   7,   1,   9

OK   OK
          i
5,   7,   1,   9

OK   OK
          i
5,   1,   7,   9

OK   OK
          i
1,   5,   7,   9

OK   OK   OK
               i
1,   5,   7,   9

OK   OK   OK   OK
               
1,   5,   7,   9

1 - Passamos começo do array (j é menor do que 0)
2 - O valor imediatamente a esquerda, é menor do que o valor sendo comparado(array[j -1] é menor do que array[j])

Implementando isso em Java, nós temos o laço que você apresentou. O segundo argumento do laço for recebe uma condição booleana que diz se o laço ainda deve ser executado, caso a avaliação da expressão retorne true o bloco de código é executado, caso retorne false, não.

A expressão pode ser a que você quiser, contanto que retorne um valor booleano, então você pode invocar diversos métodos, fazer comparações, o que quiser.

for (int j = i - 1; j >= 0 ; j--){  
    if(array[j] > a){
        array[j + 1] = array[j];  
        array[j] = a;  
    }else{
        break;
    }
}

Obrigado pessoal pela ajuda… depois dessa explicação rodrigo ficou tudo claro e a tua implementação em java ficou muito mais fácil compreender…

mostrei esse código do wikipedia pro meu professor de estrutura de dados e ele também não entendeu :oops:

[]s

javahunter:

Obrigado pessoal pela ajuda… depois dessa explicação rodrigo ficou tudo claro e a tua implementação em java ficou muito mais fácil compreender…

mostrei esse código do wikipedia pro meu professor de estrutura de dados e ele também não entendeu :oops:

[]s

Mostra o tópico aqui pra ele, pode ser útil pra ele também, quem sabe.