Lista de Projeto de algoritmos
Por: Ednelso245 • 22/4/2018 • 914 Palavras (4 Páginas) • 363 Visualizações
...
{break;}
swap(v,i,j); // troca j pelo j
}
swap(v,p,j); // troca o lado esquerda por j
return j;
}
- Quick Sort :
void quicksort( int vet[], int p, int r)
{
int j;
if( p
j = partition( vet, p, r); // chama a função paticiona
quicksort( vet, p, j-1); // se chama recursivamente
quicksort( vet, j+1, r);
}
}
Questão 31 :
Após todo esse estudo sobre os algoritmos selection, insertion sort, merge sort, quick sort, podemos entender as características, peculiaridades e curiosidades de cada um, nos seus piores, médios e melhores casos. Entretanto, o foco é compara-los, deixando mais claro tudo isso.
Dentre esses quatro algoritmos, oque mostrou ser mais eficiente foi o quick sort, considerando a sua versão três, onde o pivô é escolhido de maneira certa. Mas o merge não fica muito atrás, também demonstrou muita eficiência com sua complexidade O(nlogn) em todos os casos. Isso ocorre pois o merge sort não tem que escolher pivô, simplesmente vai dividindo o vetor em metades, diferente do quick sort, onde a escolha do pivô é de extrema importância.
Mesmo o quick sort podendo se tornar pior que o merge, ele se torna bem melhor, caso o pivô seja escolhido mais no meio do vetor possível, facilitando a ordenação. Mas, não é apenas isso que difere os dois, o quick sort não necessita de faze de combinação diferente do merge sort, explicando a vantagem do quick sort. Escolhendo o pivô de forma errada o quick sort pode chegar a uma complexidade de O(n^2), se assemelhando com o insert sort no seu pior caso e com o selection.
Levando em consideração a ineficiência, o selection chama a atenção, tendo uma complexidade de O(n^2) em todos os casos. Isso acontece pois, em qualquer situação, o código do selection terá que ser completamente executado.
E por ultimo temos o insert sort, mantendo seu bom desempenho no melhor caso, mas tendo uma complexidade de O(n^2) no médio e no pior caso. Com todas essas informações, fica bem claro onde cada um dos algoritmos se sobressai ou deixa a desejar. Sendo que esses são apenas quatro dentre muitos outros algoritmos que serão estudados futuramente.
...