Insertion sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Insertion sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso O(n^2)
complexidade caso médio O(n^2)
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-example-300px

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.[1]

Características[editar | editar código-fonte]

  • 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[editar | editar código-fonte]

Pseudocódigo[editar | editar código-fonte]

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

FUNÇÃO INSERTION_SORT (A[], tamanho)
        VARIÁVEIS      
                i, ,j
                eleito
        PARA I <- 1 ATÉ tamanho FAÇA
                eleito <- A[i];
                j <- i-1;
                ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA
                          A[j+1]:= A[j];
                          j:=j-1;
                FIM_ENQUANTO
                A[j+1] <- eleito;                
        FIM_PARA
FIM

Pseudocódigo 2[editar | editar código-fonte]

Nessa versão é acrescentada uma verificação para saber se precisa "inserir" o "eleito" na sua nova posição, ou seja, se não houve trocas, não precisa reescrever o valor, já que ele já estará no lugar certo.

FUNÇÃO INSERTION_SORT (A[], tamanho)
        VARIÁVEIS      
                i, ,j
                eleito
        PARA I <- 1 ATÉ tamanho-1 FAÇA
                eleito <- A[i];
                j <- i-1;
                ENQUANTO ((j>=0) E (eleito < A[j])) FAÇA
                          A[j+1]:=v[j];
                          j:=j-1;
                FIM_ENQUANTO
                SE ((j) <> (i-1) ENTÃO  //se for diferente teve troca de posições anteriormente
                         A[j+1] <- eleito; //escreve na nova posição
        FIM_PARA
FIM

xHarbour[editar | editar código-fonte]

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[editar | editar código-fonte]

public Long[] ordenarCrescente(Long[] array) {
    for(int fixo = 1; fixo < array.length; fixo++) {
        for (int var = fixo; var >= 1 && array[var] < array[var - 1]; var--) {
            // Troca os elementos
            array[var] += array[var - 1];
	    array[var - 1] = array[var] - array[var - 1];
	    array[var] -= array[var - 1];
        }
    }
    return array;
}

Visual Basic[editar | editar código-fonte]

    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[editar | editar código-fonte]

void insertionSort(int numeros[], int tam) {
   int i, j, eleito;
   for (i = 1; i < tam; i++){
      eleito = numeros[i];
      j = i - 1;
      while ((j>=0) && (eleito < numeros[j])) {
         numeros[j+1] = numeros[j];
         j--;
      }
      numeros[j+1] = eleito;
   }
}

Pascal[editar | editar código-fonte]

type
  t_DadosVetor = integer;
  t_vetor      = array [0..7] of t_DadosVetor;
procedure insertSort(var numeros:t_vetor; t:byte);
  var
    i,j    :byte; //ou use integer
    eleito :t_DadosVetor;
  begin
  for i:=1 to t-1 do
    begin
    eleito:=v[i];
    j:=i-1;
    while (eleito<v[j]) and (j>=0) do
      begin
      v[j+1]:=v[j];
      j:=j-1;
      end;
    v[j+1]:=eleito;
    end;
  end;

Ruby[editar | editar código-fonte]

def insertionSort(array)
   for i in 1..array.count-1
      elemento = array[i]
      j = i - 1
      while ((element < array[j]) and (j >= 0)) do
         array[j+1] = array[j]
         j = j-1
      end
    array[j+1] = elemento
  end
  p array
end

Python[editar | editar código-fonte]

def insertionSort(v):
    for j in range(1, len(v)):
        chave = v[j]
        i = j - 1
        while i >= 0 and v[i] > chave:
            v[i + 1] = v[i]
            i -= 1
        v[i + 1] = chave

Haskell[editar | editar código-fonte]

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

C#[editar | editar código-fonte]

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

PHP[editar | editar código-fonte]

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);

source

C++[editar | editar código-fonte]

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[editar | editar código-fonte]

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)
}

Lua[editar | editar código-fonte]

function insertionSort(valores)
   for i = 1, #valores do
      index = valores[i]
      j = i-1
      while ((valores[j] > index) and (j >= 0)) do
         valores[j+1] = valores[j]
         j = j-1
      end
      valores[j+1] = index
   end
end

Simulador Online[editar | editar código-fonte]

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[editar | editar código-fonte]

Referências

  1. AZEREDO, Paulo A.. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus, 1996. ISBN 85-352-0004-5

Referências[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]