C O que é insertion sort?

[UmPrograma]

Boa tarde, como vão?

 

Estava aqui estudando ordenação, aí vendo insertion sort me questionei se não era isso que já fazia.

 

Insertio sort vai organizar um vetor na ordem desejada fazendo uma comparação do primeiro com o posterior, certo?

 

E nas aulas de estrutura tinha o seguinte algoritmo como exemplo de insertion sort

typedef int key;

struct item{
    key chave;
};

typedef struct item Item;

#define troca(A, B) {Item c = A; A = B; B = c; }  // NAO ENTENDI ESSA PARTE, nem sabia que dava para fazer um programa com isso

void selection(Item *v, int n){
    int i, j, min;
    for(i = 0; i < n - 1; i++) {
        min = i;
        for(j = i + 1 ; j < n; j++) {
            if(v[j].chave < v[min].chave)
                min = j;
        }
        troca(v[i], v[min]);
    }
}

 

Antes eu faria o mesmo codigo, mais de uma forma mais simples e direta.

Segue como seria o meu codigo.

void ordenar(int vet[10]){
    int i,j, aux;
    for(i=0;i<10;i++){
        for(j=i;j<10;j++){
            if(vet[i]>vet[j]){
                aux=vet[i];
                vet[i]=vet[j];
                vet[j]=aux;
            }
        }
    }
}

 

Esse meu codigo é insertion sort ou para ser precisa ser com struct???

(aliás, nem sei a diferença das ordenações [estudei so essa por enquanto], mas parece que se muda uma coisinha já leva outro nome).

 

Me parece que tem alguma coisa de swap, numero de swap.

[isrnick]

Nenhum dos 2 códigos usam Insertion Sort (ordenação por inserção).

 

O primeiro código usa Selection Sort (ordenação por seleção), enquanto o segundo trata-se de Bubble Sort (ordenação por flutuação).

 

Vou explicar o conceito de cada um desse 3 métodos de ordenação assumindo em todos os casos que deseja-se ordenar uma lista em ordem crescente (o respectivo nome do algoritmo já é uma boa dica de como eles se comportam):

 

Selection Sort (ordenação por seleção): A partir da primeira posição da lista, para cada posição procura entre todos os itens restantes ainda não ordenados da lista qual é o de menor valor, este item encontrado com o menor valor é selecionado para ser movido para a posição atual, para isso o algoritmo faz a troca de posições do item da posição atual com o item de menor valor, assim conforme o algoritmo avança os itens de menor valor vão sendo movidos para cada posição da lista em sequência ficando em ordem crescente, e no fim a lista fica ordenada.

 

Insertion Sort (ordenação por inserção): Percorre a lista, e a cada novo item da lista move o item para a posição tal que mantém todos os itens já analisados da lista ordenados em ordem crescente, para isso conforme necessário move todos os itens analisados anteriormente com valor maior que o item atual uma posição para a frente na lista, abrindo espaço para inserir o item atual na posição correta tal que mantém todos os itens já processados ordenados, quando o último item for inserido a lista estará ordenada.

 

Bubble Sort (ordenação por flutuação): Percorre a lista várias vezes, comparando cada 2 itens consecutivos da lista, e trocando as posições dos itens se o primeiro item tiver valor maior que o segundo, então os números maiores são movidos para o fim da lista, e a cada vez que termina de percorrer a lista inteira o maior número da lista "flutua" para o fim da lista, e os números maiores vão sendo ordenados do fim da lista para o começo. Se percorrer a lista inteira e nenhuma troca for feita pode parar de percorre-la pois ela já está ordenada, ou então pode parar após percorrer N vezes uma lista com N itens pois essa é a quantidade máxima de vezes que precisa para ordenar todos os itens.

[Flávio Pedroza]

#define troca(A, B) {Item c = A; A = B; B = c; }

Isto é um MACRO. Basicamente ele vai "copiar" o que está entre chaves em seu código fonte toda vez que você invocar a macro.

então 

void selection(Item *v, int n){
    ...
        troca(v[i], v[min]);
    }
}

É transformado pelo compilador em:

void selection(Item *v, int n){
    ...
		Item c = v[i]; v[i] = v[min]; v[min] = c;        
    }
}

São usadas para definir constantes ou trechos de código que serão repetidos várias vezes. 

[UmPrograma]

@Flávio Pedroza  Valeu..

 

Eu estava tentando fazer isso com strings, mas acho que não funcionou direito.

 

Brigadão.....