Estrutura de dados e o Insertion Sort

Insertion Sort. Técnica de organização de vetores. Usando sempre a estrutura de dados a nosso favor!

Exemplo de Insertion Sort. Estrutura de dados para organizar vetores!

   Olá novamente nerds! Ok, ok, e desenvolvedores! Ah claro, também programadores.
   Vou continuar com a sequência de matérias sobre desenvolvimento, pois já estou com elas preparadas aqui em rascunho mas não posso publicar todas de uma vez, afinal, precisamos de um suspense, correto?

   Brincadeiras a parte para descontrair, vou postar hoje sobre um algoritmo bem parecido com o que postei anteriormente, mas que tem maior rapidez do que o outro quando usado em vetores uni dimensionais pequenos. Esse algoritmo também tem ordem de complexidade O(n²). Mas o que exatamente o Insertion Sort faz? Usando os mesmos valores do vetor usado no algoritmo do Selection Sort, que caso não tenha lido pode clicar aqui e lê-lo, ele irá também ordenar os valores da esquerda para a direita, considerando o primeiro valor como o menor send que a diferença o Insertion Sort para o Selection Sort, que as vezes é meio complicado para alguns entenderem, é que ele, conforme vai andando pelo vetor, volta reordenando os valores para trás. Ou seja, em poucas palavras, ele vai andando da esquerda pra direita e conforme vai avançando para a direita, vai reordenando os valores que estão pra trás, caso necessário.
   Abaixo, para melhor visualização, vou mostrar o algoritmo também usando os mesmos valores do algoritmo do exemplo passado e acima, podem tentar visualizar a resolução pela imagem de exemplo.

#include;
#include;

//definicao do vetor para 10 valores
#define MAX 10

main(){
    int i;
    int j;
    int aux;
    int vet[MAX] = {8, 5, 6, 3, 54, 65, 3, 5, 765, 1};

    /*loop para interacao de percorrer todo o vetor. Diferentemente
    do outro algoritmo, nesse o loop vai ate n e nao ate n-1.*/
    for(i = 1; i < MAX; i++){

        /*definicao de aux para o segundo valor do vetor.
        note que no loop acima, i comeca de 1 e nao de 0*/
        aux = vet[i];

        //o j tera o valor da primeira posicao do vetor
        j = i -1;

        /*esse while ira acontecer enquanto j for maior que -1,
        ou seja, 0, e o valor do vetor atualmente for maior do
        que o valor de aux, que e o menor valor no momento.
        Ou seja, se entrar no while, significa que achou um valor
        menor do que aux e que ele ira ser substituido para a
        esquerda (voltando) ate que chegue em algum valor que seja
        maior que aux ou que ele chegue a primeira posicao do vetor
        indicando entao que, naquela volta do loop, o valor
        encontrado foi o menor ate o momento.*/
        while((j > -1) && (vet[j] > aux)){

            /*aqui o valor sera invertido, j decrementado e a menor
            posicao, que ja foi trocada, sera atribuida a aux*/
            vet[j + 1] = vet[j];
            j--;
            vet[j + 1] = aux;
        }
    }
}

   Assim, apenas para ficar claro. Para um vetor uni dimensional e pequeno, até o momento, usa-se o Insertion Sort. Para qualquer outro vetor uni dimensional do tamanho que for, usa-se o Selection Sort, pois não temos como saber o quanto o vetor está ordenado.
   Os aguardo então na próxima matéria sobre desenvolvimento, senhores programadores e desenvolvedores, pois começaremos realmente com algoritmos interessantes, falando por exemplo sobre Bubble Sort, Quick Sort e Merge Sort, que são os que pretendo mostrar para vocês e que também são os mais utilizados.
   Obrigado novamente pela leitura e acompanhamento e continuem promovendo o blog!