Insertion Sort

Definição

Insertion Sort, ou ordenação por inserção, é o algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação.

Podemos fazer uma comparação do Insertion Sort com o modo de como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam a ordenação.

A cada nova carta adicionada a sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até você não receber mais cartas.

Esta é a ideia por trás da ordenação por inserção. Percorra as posições do array, começando com o índice 1 (um). Cada nova posição é como a nova carta que você recebeu, e você precisa inseri-la no lugar correto no subarray ordenado à esquerda daquela posição.

Características

Apesar de ser menos eficiente que algoritmos como Merge Sort e Quick Sort (de ordem O(nlog(n))), o Insertion Sort possui algumas características consideráveis:

- É de simples implementação, leitura e manutenção;
- In-place: Apenas requer uma quantidade constante de O(1) espaço de memória adicional;
- Estável: Não muda a ordem relativa de elementos com valores iguais;
- Útil para pequenas entradas;
- Muitas trocas, e menos comparações;
- Melhor caso: O(n), quando a matriz está ordenado;
- Médio caso: O(n²/4), quando a matriz tem valores aleatórios sem ordem de classificação (crescente ou decrescente);
- Pior caso: O(n²), quando a matriz está em ordem inversa, daquela que deseja ordenar.

Vantagens

- É o método a ser utilizado quando o arquivo está "quase" ordenado
- É um bom método quando se desejar adicionar poucos elementos em um arquivo já ordenado, pois seu custo é linear.
- O algoritmo de ordenação por inserção é estável.

Desvantagens

- Alto custo de movimentação de elementos no vetor.

Implementação do método Insertion Sort

Código:


void insertion_sort (int arr[], int length){
       int j, temp;
      
   for (int i = 0; i < length; i++){
      j = i;
      
      while (j > 0 && arr[j] < arr[j-1]){
           temp = arr[j];
           arr[j] = arr[j-1];
           arr[j-1] = temp;
           j--;
           }
      }
}

Vídeos para reforços (ABRA O SPOILER):

Atividade de Fixação (ABRA O SPOILER):