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] Pseudocódigo
Segue uma versão simples do pseudocódigo do algoritmo, com vetores começando em zero:
insere(array vetor, int tamanho, valor) {
int i = tamanho - 1;
while (i >= 0 && vetor[i] > valor) {
vetor[i + 1] = vetor[i];
i--;
}
vetor[i + 1] = valor;
}
insertionSort(array vetor, int tamanho) {
for (int i = 1; i < tamanho; i++) insere(vetor, i, vetor[i]);
}
/**
* Ou isso...
*
* @author Pedro Amorim - Campina Grande
*/
InsertionSort(V, n)
for j← 2 to n do
aux ← V[j]
► insere V[j] na parte ordenada V[1..j-1]
i ← j – 1
while i > 0 e V[i] > aux do
V[i + 1] ← V[i]
i ← i – 1
V[i + 1] ← aux
[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;
}
}
/**
* InsertionSort
*
* @author Pedro Amorim - Campina Grande
*/
public static void insertionSort(int[] vetor) {
for (int i = 0; i < vetor.length; i++) {
int aux = vetor[i];
int j = i;
while (j > 0 && vetor[j - 1] > aux) {
vetor[j] = vetor[j - 1];
j = j - 1;
}
vetor[j] = aux;
}
}
[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[], int 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+1] = value;
}
}
InsertionSort, Ordenação com strings:
void ordenar_insercao_nome()
{
for (l=1;l<n;l++)
{
t = l;
while (strcmpi(vetor[t],vetor[t-1])<0 && t>0)
{
strcpy (aux_char,vetor[t]);
strcpy (vetor[t],vetor[t-1]);
strcpy (vetor[t-1],aux_char);
t--;
}
}
}
[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.
