Insertion sort
Origem: Wikipédia, a enciclopédia livre.
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.
Índice |
[editar] Características
- Menor número de trocas e comparações entre os algoritmos de ordenação Ω(n) quando o vetor está ordenado.
- Pior caso Θ(n2)
[editar] Implementações
[editar] Java
private static void insertionSort(int[] v) {
for (int i = 1; i < v.length; i++) {
int value = v [i], j = i - 1;
while ( j >= 0 && value < v [j] ) {
v[j + 1] = v [j];
j--;
}
v[j + 1] = value;
}
}
[editar] Visual Basic
Dim j As Integer
For i As Integer = 1 To Array.GetUpperBound(0)
j = i - 1
Dim Value As Integer = Array(i)
While j >= 0 And Array(j) > Array(i)
Array(j + 1) = Array(j)
j -= 1
End While
Array(j + 1) = Value
Next
[editar] C
void insertSort(int a[], size_t length) {
int i, j, value;
for(i = 1; i < length; ++i) {
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; --j) {
a[j + 1] = a[j];
a[j] = value;
}
}
}
[editar] Pascal
procedure InsertSort(var v:VetEntrada;FimDoVetor:integer);
var cont, down, swp: integer;
begin
for cont := 1 to FimDoVetor do
begin
swp := v[cont] ;
down := cont - 1 ;
while (down >= 1 ) and (swp < v[down]) do
begin
v[down + 1] := v[down];
down := down - 1;
end;
v[down + 1] := swp;
end;
end;
[editar] Python
def InsertionSort(list):
n=len(list)
for i in range (1,n):
swp=list[i]
j=i-1
while j>=0 and swp<list[j]:
list[j+1]=list[j]
j=j-1
list[j+1]=swp
print list
[editar] Haskell
insert :: Ord a => a -> [a] -> [a]
insert item [] = [item]
insert item (h:hs) | item <= h = item:h:hs
| otherwise = h:(insert item hs)
insertsort :: Ord a => [a] -> [a]
insertsort [] = []
insertsort (h:hs) = insert h (insertsort hs)
[editar] 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.
