Insertion sort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Foi acrescido mudanças na definição da descrição do algoritmo Insertion Sort. Etiquetas: Referências removidas Editor Visual |
Adição do parágrafo "Comparação com outros algoritmos de ordenação por comparação e troca." |
||
Linha 30:
* Médio caso: O(n²/4), quando a matriz tem valores aleatórios sem ordem de classificação (crescente ou decrescente);
* Pior caso: O(n²), quando a matriz está em ordem inversa, daquela que deseja ordenar.
== Comparação com outros algoritmos de ordenação por comparação e troca ==
Em termos de comparação com outros algoritmos de ordenação, o Insertion sort e o Bubble sort atingem O(n) em seus melhores casos, diferente do Selection sort que é O(n²) em todos os seus casos (melhor, médio e pior caso).
{| class="wikitable sortable"
!Algoritmo
! colspan="3" |Complexidade
|-
|
|Melhor
|Médio
|Pior
|-
|Insertion sort
|O(n)
|O(n<sup>2</sup>)
|O(n<sup>2</sup>)
|-
|Bubble sort
|O(n)
|O(n<sup>2</sup>)
|O(n<sup>2</sup>)
|-
|Selection sort
|O(n<sup>2</sup>)
|O(n<sup>2</sup>)
|O(n<sup>2</sup>)
|}
Obs.: O BubbleSort atinge O(n) em seu melhor caso, quando o vetor já está inteiramente ordenado! Então é necessário apenas uma verificação básica sobre todo o vetor, o que representa um custo de O(n).
== Implementações ==
| |||