Os Algoritmos de Ordenação
Por: SergioXD97 • 7/11/2021 • Trabalho acadêmico • 422 Palavras (2 Páginas) • 151 Visualizações
Selection sort
Este algoritmo consiste em passar sempre o menor (ou maior, depende da ordem requisitada) valor do vetor para a primeira posição e depois o segundo menor valor para a segunda posição e assim vai indo até os dois últimos elementos.
Neste algoritmo é escolhido um número a partir do primeiro e então este número é comparado com os números da sua direita e quando encontra um número menor eles trocam de lugar. E então este número encontrado será o próximo número escolhido, caso não for encontrado nenhum número menor que este escolhido, ele é colocado na posição do primeiro número escolhido, e o próximo número à sua direita vai ser o escolhido para fazer as comparações. É repetido esse processo até que a lista esteja ordenada. [pic 1][pic 2][pic 3]
Insertion Sort
Este algoritmo é mais simples e mais eficiente quando aplicado em pequenas listas. Este algoritmo consiste em percorrer a lista da esquerda para a direita, conforme vai passando ele deixa os elementos mais à esquerda ordenados.
Um exemplo dele em nossas vidas é quando ordenamos cartas em um jogo de baralho como pôquer ou UNO.
[pic 4]
[pic 5]
Quick Sort
O algoritmo Quick Sort é o mais eficiente na ordenação por comparação. Nele é escolhido um elemento chamado de pivô, a partir disso a lista é organizada para que todos os números antes dele sejam menores que ele e todos os números depois dele sejam maiores que ele. Ao final do processo o número pivô já se encontra na sua posição final.
[pic 6]
[pic 7]
[pic 8]
Testes
Os testes foram realizados em 3 tamanhos diferentes de vetores, 100, 1.000 e 10.000.
Os resultados foram os seguintes:
VETOR 100 | |
Algoritmo | Tempo(ms) |
Selection Sort | 0,06 |
Insertion Sort | 0,0038 |
Quick Sort | 0,0141 |
VETOR 1.000 | |
Algoritmo | Tempo(ms) |
Selection Sort | 5 |
Insertion Sort | 0,035 |
Quick Sort | 0,1 |
VETOR 10.000 | |
Algoritmo | Tempo(ms) |
Selection Sort | 508 |
Insertion Sort | 0,35 |
Quick Sort | 2 |
Conclusão:
Em nosso teste o Selection Sort foi o pior em tempo dentre os 3 vetores testados.
Insertion Sort teve o melhor tempo entre os 3.
...