Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de ordenação de dados (Métodos simples (2.1 Insertion Sort…
Algoritmos de ordenação de dados
Introdução
buscar um número em uma lista telefônica se o nome das pessoas não estivessem em ordem alfabética
ordenação
: organiza os registros em ordem crescente ou decrescente para facilitar a recuperação desses dados
Métodos simples
adequados para pequenos vetores
são programas pequenos e fáceis de entender
possuem complexidade C(n)=O(n^2), onde n é o número de registros; ordem quadrática; n^2 comparações nos piores casos
2.1 Insertion Sort
percorre um vetor de elementos da esquerda para a direita e à medida que avança vai ordenando os elementos à esquerda
possui complexidade C(n)=O(n) no melhor caso e C(n)=O(n^2) no médio e pior caso
2.2 Selection Sort
consiste em selecionar o menor item e colocar na primeira posição, selecionar o segundo e colocar na segunda posição e segue esses passos até que reste só um elemento
para todos os casos possui complexidade C(n)=O(n^2)
2.3 Bubble Sort
percorre o vetor diversas vezes, e a cada passagem faz flutuar para o topo o maior elemento da sequência
no melhor caso, o algoritmo executa n operações relevantes; no pior caso, são feitas n^2 operações
Métodos eficientes
3.1 Quick Sort
emprega a estratégia de "divisão e conquista"
a) escolhe um elemento da lista chamado "pivô"
b) particionamento: reorganiza a lista de forma que os elementos menores que o pivô fiquem de um lado, e os maiores fiquem de outro
c) recursivamente ordena a sub-lista abaixo e acima do pivô.
possui complexidade C(n)=O(n^2) no pior caso e C(n)=O(n log n) no melhor e médio caso
3.2 Merge Sort
"dividir para conquistar"
o vetor é dividido em duas partes iguais, que serão divididas em duas partes, e assim até ficar um ou dois elementos cuja a ordenação é trivial
para juntar as partes ordenadas, os dois elementos de cada parte são separados e o menor deles é selecionado e retirado de sua parte
em seguida, os menores entre os restantes são comparados e assim se prossegue até juntar as partes
possui complexidade C(n)=O(n log n) para todos os casos
são mais complexos, mas requerem menor número de comparações
são projetados para trabalhar com uma quantidade maior de dados e possuem complexidade C(n)=O(n log n)
Conclusão
algoritmos eficientes devem ser preferidos para problemas de maior escala
