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
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso total, 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-1) 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

[editar | editar código-fonte]

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]

int *InsertionSort(int original[], int length)
{
	int i, j, atual;

	for (i = 1; i < length; i++)
	{
		atual = original[i];
		j = i - 1;

		while ((j >= 0) && (atual < original[j]))
		{
			original[j + 1] = original[j];
            j = j - 1;
		}
    
		original[j + 1] = atual;
	}

	return (int*)original;
}

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 ((elemento < 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

Java[editar | editar código-fonte]

public class InsertionSort {

	public static void main(String[] args) {

		int[] numeros = new int[5];

		numeros[0] = 3;
		numeros[1] = 5;
		numeros[2] = 4;
		numeros[3] = 2;
		numeros[4] = 1;

		for (int num : insertionSort(numeros)) {
			System.out.print(num + " - ");
		}

	}

	public static int[] insertionSort(int[] numeros) {

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

Go[editar | editar código-fonte]

func Sort(list []int) []int {
    for j := range list {
        key := list[j]
        i := j - 1
	for i >= 0 && list[i] > key {
	    list[i + 1] = list[i]
	    i -= 1
	}
	list[i + 1] = key
    }
    return list 
}

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. (1996). Métodos de Classificação de Dados e Análise de suas Complexidades (Rio de Janeiro: Campus). ISBN 85-352-0004-5. 

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

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