Algoritmos e Estruturas de Dados/Selection e Insertion

Insertion

Implementações

Pseudocódigo

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

 INSERTION_SORT(A, size) 
         for  j ←2  to  size do 
                key  ← A[ j] 
                i  ← j –1 
                while  i > 0  and  A[i] > key  do 
                         A[i+1]  ← A[i] 
                         i  ← i –1 
        A[i+1]          ←  key 

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 Integer[] insertionSort(Integer[] 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 *primeiro, int *ultimo)
{
  int aInserir, *posAIncio + 1, *posAtual;
  for (; posAInsir <= ulmo; ++posAInserir)
  {
    aInserir = *posAInserir;
    posAtual = posArir - 1;
    while (Atual >= priro && *posAtual > aerir )
    {
      *(posAtu+1) = *posAtual;
      --posal;
    }
    *(posl+1) = aInserir;
  }
}

Outra versão em C:

void insertionSort(int v[], int n)
{
	int i, j, chave;
	
	for(j=1; j<n; j++) 
	{
		chave = v[j];
		i = j-1;
		while(i >= 0 && v[i] > chave)
		{
			v[i+1] = v[i];
			i--;
		}		
		v[i+1] = chave;
	}
}

Pascal

procedure InsertionSort(var a:vetor; n:integer; var NC, NT: integer);
var j,o: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);
  troca(a[j],a[o]);
  j:=i-1;
  o:=o-1;
  inc(NC);
 end;
 end;
end;

Python

def inssort(v):
    for j in range(1, len(v)):
        key = v[j]
        i = j - 1
        while a[i] > key and i >= 0:
            a[i+1] = a[i]
            i -= 1
        v[i+1] = 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

/**
 * @author Nissius Guilet Ribas
 * @copyright 2009
 *
 * Correção, no while, não é j>=0 e sim j>0;
 */

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