Implementação de algoritmos de ordenação Insertion Sort e Bubble Sort em C, comparação do tempo de ordenação entre as duas técnicas.
A partir dos dados coletados, observa-se que o método de ordenação Insertion concluiu mais rapidamente a ordenação dos vetores em todos os cenários. A complexidade dos dois métodos é semelhante (o tempo de ordenação aumenta exponencialmente conforme o tamanho do vetor aumenta), já que há um laço de repetição dentro de outro no código em ambos os casos. Bubble faz mais comparações, aproximadamente j²/2 iterações (em que j é o número de elementos do vetor), enquanto Insertion faz aproximadamente j²/4 iterações.Para testar o algoritmo, o programa em C foi executado 3 vezes para cada tamanho de vetor supracitado e média do tempo de execução foi calculada.
Dessa forma, é possível concluir que estes dois algoritmos são indicados para menores conjuntos de dados. Além disso, apesar de um pouco mais complexo, nas situações descritas, Insertion é mais eficaz.
| Média | ||
| v[ ] | Bubble | Insertion |
| 50000 | 5.3 | 1.6 |
| 100000 | 25 | 7 |
| 200000 | 114.3 | 26 |
| 400000 | 470 | 105.3 |
| 800000 | 1798.3 | 404.6 |
| 1600000 | 6724 | 1462.3 |
| Resultados Obtidos | |||
| Tempo (s) | |||
| v[ ] | Execução # | Bubble | Insertion |
| 50000 | 1 | 6 | 2 |
| 50000 | 2 | 5 | 1 |
| 50000 | 3 | 5 | 2 |
| Média | 5.333333333 | 1.666666667 | |
| 100000 | 1 | 25 | 7 |
| 100000 | 2 | 26 | 7 |
| 100000 | 3 | 24 | 7 |
| Média | 25 | 7 | |
| 200000 | 1 | 114 | 26 |
| 200000 | 2 | 114 | 26 |
| 200000 | 3 | 115 | 26 |
| Média | 114.3333333 | 26 | |
| 400000 | 1 | 469 | 106 |
| 400000 | 2 | 471 | 105 |
| 400000 | 3 | 470 | 105 |
| Média | 470 | 105.3333333 | |
| 800000 | 1 | 1828 | 408 |
| 800000 | 2 | 1822 | 409 |
| 800000 | 3 | 1745 | 397 |
| Média | 1798.333333 | 404.6666667 | |
| 1600000 | 1 | 6842 | 1438 |
| 1600000 | 2 | 6710 | 1426 |
| 1600000 | 3 | 6620 | 1523 |
| Média | 6724 | 1462.333333 | |