Insertion sort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
| Linha 132: | Linha 132: | ||
v[i]=aux; |
v[i]=aux; |
||
} |
} |
||
//@autor Emanuel Batista |
|||
} |
} |
||
</source> |
</source> |
||
Revisão das 19h56min de 29 de maio de 2014
| 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 | |
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
- 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
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
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
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
public Long[] ordenarCrescente(Long[] array){
for(int fixo = 1; fixo <= array.length; fixo++){
int x = fixo - 1;
int y = fixo;
while(y != 0 && y != array.length && array[x] > array[y]){
Long a = array[x];
array[x] = array[y];
array[y] = a;
x--;
y--;
}
}
return array;
}
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
void insertion_sort(int v[],int size){
int k,i,aux;
for(k=1;k<size;k++){
aux=v[k];
for(i=k;i>0 && v[i-1]>aux;i--){
v[i]=v[i-1];
}
v[i]=aux;
}
//@autor Emanuel Batista
}
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;
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
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
import Data.List (insert)
insertsort :: Ord a => [a] -> [a]
insertsort = foldr insert []
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;
}
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
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;
}
}
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)
}
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
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
Referências
- ↑ 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
- 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.