- LukinhaAdmin
- Mensagens : 5
Pontos : 17
Reputação : 2
Data de inscrição : 05/05/2017
Idade : 33
Localização : Bandeirantes
MergeSort - Método de Ordenação
Seg Nov 13, 2017 1:55 pm
Definição
Figura 1. Esquema de funcionamento do MergeSort
Performances:
Melhor caso: O(N log N).
Pior caso (raro): O(N log N).
Operações do Algoritmo
Função Intercala
Função de Ordenação
Main
Videos para reforços ( ABRA OS SPOILERS )
ATIVIDADE DE FIXAÇÃO ( ABRA O SPOILER )
Algoritmo de ordenação é baseado primeiramente em selecionar um elemento, dividir a lista e então, ordenar-las separadamente. E posteriormente há um processo complementar o qual é chamado de junção. O processo de Seleção e junção são complementares porque:
Seleção: divide a lista em 2 outras independentes. Junção: une 2 listas independentes em uma lista maior ordenada.
Isso insinua que o Mergesort consiste em duas chamadas recursivas e um processo de junção. Então, Mergesort é um algoritmo recursivo, que é implementado dividindo uma sequência original em pares de dados, ordena-as e depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes. Assim, sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas.
O mergeSort consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente.
Esta técnica realiza-se em três fases:
1 - Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
2 - Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
3 - Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn).
Seleção: divide a lista em 2 outras independentes. Junção: une 2 listas independentes em uma lista maior ordenada.
Isso insinua que o Mergesort consiste em duas chamadas recursivas e um processo de junção. Então, Mergesort é um algoritmo recursivo, que é implementado dividindo uma sequência original em pares de dados, ordena-as e depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes. Assim, sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas.
O mergeSort consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente.
Esta técnica realiza-se em três fases:
1 - Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
2 - Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
3 - Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn).
Figura 1. Esquema de funcionamento do MergeSort
Performances:
Melhor caso: O(N log N).
Pior caso (raro): O(N log N).
Função Intercala
- Código:
void intercala(int *X, int ini, int fim, int meio){
int poslivre, ini_v1, ini_v2, i, aux[10];
ini_v1=ini;
ini_v2=meio+1;
poslivre=ini;
while(ini_v1<=meio && ini_v2<=fim){
if(X[ini_v1]<=X[ini_v2]){
aux[poslivre]=X[ini_v1];
ini_v1++;
}
else{
aux[poslivre]=X[ini_v2];
ini_v2++;
}
poslivre++;
}
for(i=ini_v1; i<=meio; i++){
aux[poslivre]=X[i];
poslivre++;
}
for(i=ini_v2; i<=fim; i++){
aux[poslivre]=X[i];
poslivre++;
}
for(i=ini; i<=fim; i++){
X[i]=aux[i];
}
}
Função de Ordenação
- Código:
void merge(int *X, int ini, int fim){
int meio;
if(ini<fim){
meio=(int)floor((ini+fim)/2);
merge(X, ini, meio);
merge(X, meio+1, fim);
intercala(X, ini, fim, meio);
}
}
Main
- Código:
int main()
{
int X[10], i;
for(i=0; i<10; i++){
printf("\nDigite o %do elemento: ", i+1);
scanf("%d",&X[i]);
}
printf("\n\n Desordenado");
for(i=0; i<10; i++) printf("\t%d", X[i]);
merge(&X[0], 0, 9);
printf("\n\n Ordenado");
for(i=0; i<10; i++) printf("\t%d", X[i]);
return 0;
}
Videos para reforços ( ABRA OS SPOILERS )
- MergeSort Método de Ordenação:
ATIVIDADE DE FIXAÇÃO ( ABRA O SPOILER )
- Spoiler:
Permissões neste sub-fórum
Não podes responder a tópicos
|
|