Insertion sort

Insertion sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	O(n2)
complexidade caso médio	O(n2)
complexidade melhor caso	O(n)
complexidade de espaços pior caso	O(n) total, O(1) auxiliar
estabilidade	estável
Algoritmos

Exemplo de funcionamento do insertion sort em uma lista de inteiros aleatórios

Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.

Características

• Menor número de trocas e comparações entre os algoritmos de ordenação O(n) quando o vetor está ordenado.
• Pior caso O(n²)

Implementações

Pseudocódigo

Segue uma versão simples do pseudocódigo do algoritmo, com vetores começando em zero:

FUNCAO INSERTION_SORT (A[], tamanho)

        VARIAVEIS
        var i, j, elemento;
        
        
        PARA j <- 0 ATÉ tamanho - 1 FAÇA
                elemento <- A[j];
                i <- j – 1;
                
                ENQUANTO ((i >= 0) E (A[i] > elemento)) FAÇA
                        A[i+1] <- A[i]
                        A[i] <- elemento
                        i <- i–1
                FIM_ENQUANTO
                
        FIM_PARA
        
FIM

xHarbour

Function SortInsertion( aList )
   Local nLoop1 := 0
   Local nLoop2 := 0
   Local nIndex := 0
   For nLoop1 := 1 To Len( aList )
       nLoop2 := nLoop1
       nIndex := aList[ nLoop1 ]
       While nLoop2 > 1 .And. aList[ nLoop2 - 1 ] > nIndex
          aList[ nLoop2 ] := aList[ nLoop2 - 1 ]
          nLoop2 --
       EndDo
       aList[ nLoop2 ] := nIndex
   Next
Return NIL

Java

        public static int[] insertionSort(int[] array) 
         {
                for (int i = 1; i < array.length; i++) 
                {
                        int a = array[i];
                        int j;
                        for (j = i - 1; j >= 0 && array[j] > a; j--)
                        {
                                array[j + 1] = array[j];
                                array[j] = a;
                        }
                }
                return array;
        }

Visual Basic

    Private Sub Ordenacao(Numeros() As Integer)
       Dim i As Long
       Dim j As Long
       Dim iMin As Long
       Dim iMax As Long
       Dim varSwap As Variant
       iMin = LBound(Numeros) + 1
       iMax = UBound(Numeros)
       For i = iMin To iMax
           varSwap = Numeros(i)
           For j = i To iMin Step -1
               If varSwap < Numeros(j - 1) Then Numeros(j) = Numeros(j - 1) Else Exit For
           Next j
          Numeros(j) = varSwap
       Next i
End Sub
'Code By Kalandar

C

void insertionSort(int v[], int tam)
{         
        int i, j, aux;
 
        for(i = 1; i < tam; i++){
 
                j = i;
 
                while(V[j] < V[j - 1]) {
 
                        aux = V[j];
                        V[j] = V[j - 1];
                        V[j - 1] = aux;
                        j--;   
 
                        if(j == 0)break;
                }         
        }
 
        return;
}

Pascal

procedure InsertionSort(var vet:array[1..20] of integer; n:integer; var NC, NT: integer);
var j,o,aux:integer; {variaveis auxiliares}
begin
  for j:=2 to n do
  begin
    o:=j-1;
    while (a[j]<a[o]) and (i>1) do
    begin
      inc(NT);
      aux:=a[j];
      a[j]:=a[o];
      a[o]:=aux;
      j:=i-1;
      o:=o-1;
      inc(NC);
    end;
  end;
end;

Python

def inssort(l):
    for i in range(1, len(l)):
        key = l[i]
        j = i
        while j > 0 and l[j - 1] > key:
            l[j] = l[j - 1]
            j -= 1
        l[j] = key

Haskell

import Data.List (insert)
 
insertsort :: Ord a => [a] -> [a]
insertsort = foldr insert []

C#

   static int[] ordernar(int[] A)
   { 
      int i, j, index;
      for (i = 1; i < A.Length; i++)
      {
          index = A[i];
          j = i;
          while ((j > 0) && (A[j - 1] > index))
          {
              A[j] = A[j - 1];
              j = j - 1;
          }
          A[j] = index;
      }
      return A;
   }

PHP

ini_set('max_execution_time','600');
 
function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}
 
 
for ($gera = 0; $gera <=20000; $gera++){
        $array[$gera] = rand(0, 10000);
}
 
$time_start = microtime_float();
for($i = 1; $i < count($array); $i++){
        $copiado = $array[$i];
        $j = $i;
                while (($j > 0 ) && ($copiado < $array[$j-1])){
                        $array[$j] = $array[$j-1];
                        $j--;
                }
                $array[$j] = $copiado;   
}
$time_end = microtime_float();
//Mostra o tempo que levou para ordenar
echo $time = $time_end - $time_start;
 
//Exibe a ordenação
print_r ($array);

C++

void Inserction(int n, int vetor[]){
   int j,i,key;
   for(j = 1; j < n; j++){
      key = vetor[j];
      i = j - 1;
      while(i >= 0 && vetor[i] > key){
         vetor[i + 1] = vetor[i];
         i = i - 1;
      }
      vetor[i + 1] = key;
   }
}

R

insertSort <- function(vec) {
  for(i in 1:length(vec)) {
    key <- vec[i]
    j <- i
    while(j > 1 && vec[j - 1] > key) {
      vec[j] <- vec[j - 1]
      j <- j - 1
    }
    vec[j] <- key
  }
  return(vec)
}

Simulador Online

Para um melhor entendimento, recomendo utilizarem o Simulador Online para visualizarem exemplos de ordenação de números aleatórios pelo Insertion Sort.

Ver também

• Selection sort
• Bubble sort

Referências

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 2.1: Insertion sort, pp. 15–21.

Ligações externas

• Uma animação em Java mostrando passo-a-passo a implementação do insertion sort.
• Pesquisa e Ordenação