Ordenação por Intercalação
Ddrv utfpr (disc | contribs) |
Ddrv utfpr (disc | contribs) (→Características) |
||
(27 edições intermediárias de um usuário não apresentadas) | |||
Linha 1: | Linha 1: | ||
− | + | Ordenação por intercalação (Merge Sort) é um algoritmo de ordenação muito utilizado em computação, criado pelo matemático húngaro John von Neumann (1903-1957). | |
+ | |||
+ | == Princípio de Funcionamento == | ||
+ | |||
+ | O princípio básico de funcionamento do Merge Sort é simples e intuitivo: o algoritmo divide a lista a ser ordenada em várias sublistas, sempre em duas partes, até que as listas restantes contenham apenas um elemento. Após esta divisão o algoritmo faz o caminho inverso, ou seja, ele começa a "remontar" o vetor, porém ordenando os elementos (que estão em menor número) enquanto os vetores maiores são recriados. | ||
+ | |||
+ | == Características == | ||
+ | |||
+ | * O Merge Sort necessita de um vetor auxiliar para funcionar, de tamanho igual ao do vetor a ser ordenado, o que constitui uma desvantagem deste algoritmo. | ||
+ | |||
+ | * Sua complexidade é nlog<sub>2</sub>n (pior caso), sendo n o número de elementos que serão ordenados. | ||
+ | |||
+ | * O Merge Sort é considerado como o melhor algoritmo de ordenação já inventado, devido à sua simplicidade e eficiência. | ||
+ | |||
+ | * Alto consumo de memoria, devido à série de chamadas recursivas. | ||
+ | |||
+ | * Por ser mais complexo que os outros algoritmos de ordenação, ele só é realmente mais rápido na prática quando n for suficientemente grande. | ||
+ | |||
+ | == Exemplo == | ||
+ | Segue abaixo um exemplo de aplicação do Merge Sort para ordenar um vetor de 8 elementos: | ||
+ | |||
+ | 15 99 52 14 50 64 20 77 | ||
+ | |||
+ | Divisão em duas partes: | ||
+ | |||
+ | 15 99 52 14 - 50 64 20 77 | ||
+ | |||
+ | Divisão da primeira parte em duas outras partes: | ||
+ | |||
+ | 15 99 - 52 14 | ||
+ | |||
+ | Análise do primeiro par: | ||
+ | |||
+ | 15- 99 | ||
+ | |||
+ | Como 15 é menor do que 99, a ordem é mantida. | ||
+ | |||
+ | Análise do segundo par: | ||
+ | |||
+ | 52 -14 | ||
+ | |||
+ | Como 52 é maior do que 14, a ordem é invertida: | ||
+ | |||
+ | 14 -52 | ||
+ | |||
+ | Agora restam dois pares ordenados: | ||
+ | |||
+ | 15 99 - 14 52 | ||
+ | |||
+ | O algoritmo agora compara o menor valor de cada um dos dois vetores: | ||
+ | |||
+ | 15 -14 | ||
+ | |||
+ | Como 14 é menor do que 15, esse valor será o primeiro da lista de 4 elementos: | ||
+ | |||
+ | 14 X X X | ||
+ | |||
+ | Compara-se 15 com o outro elemento do segundo vetor. Como 15 é menor do que 52, 15 ocupará a segunda posição: | ||
+ | |||
+ | 14 15 X X | ||
+ | |||
+ | Agora simplesmente comparam-se os dois elementos restantes. 99 é maior do que 52, logo 52 ocupará a terceira posição, e 99 a quarta posição neste vetor de 4 elementos: | ||
+ | |||
+ | 14 15 52 99 | ||
+ | |||
+ | O processo é repetido de forma idêntica para a outra primeira metade do vetor inicial, que apresentará a seguinte configuração: | ||
+ | |||
+ | 20 50 64 77 | ||
+ | |||
+ | Neste ponto tem-se dois vetores ordenados: | ||
+ | |||
+ | 14 15 52 99 - 20 50 64 77 | ||
+ | |||
+ | O próximo e último passo é fazer a fusão destes dois vetores, de forma similar àquela já feita, comparando o menor elemento de cada um dos dois vetores e posicionando o menor elemento ordenadamente na lista original. | ||
+ | |||
+ | Feito este processo, o resultado final será: | ||
+ | |||
+ | 14 15 20 50 52 64 77 99 | ||
+ | |||
+ | |||
+ | == Implementação em C: == | ||
+ | |||
+ | <pre> | ||
+ | void mergeSort(int vetor[],int aux[],int tam) { | ||
+ | m_sort(vetor,aux,0,tam-1); | ||
+ | } | ||
+ | |||
+ | void merge(int vetor[],int aux[],int esq,int meio,int dire) { | ||
+ | |||
+ | int i,esq_fim,num_elementos,aux_pos; | ||
+ | |||
+ | esq_fim=meio-1; | ||
+ | aux_pos=esq; | ||
+ | num_elementos=dire-esq+1; | ||
+ | |||
+ | while ((esq<=esq_fim)&&(meio<=dire)) { | ||
+ | |||
+ | if (vetor[esq]<=vetor[meio]) { | ||
+ | |||
+ | aux[aux_pos]=vetor[esq]; | ||
+ | aux_pos=aux_pos+1; | ||
+ | esq=esq+1; | ||
+ | } | ||
+ | else { | ||
+ | |||
+ | aux[aux_pos]=vetor[meio]; | ||
+ | aux_pos=aux_pos + 1; | ||
+ | meio=meio+1; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | while (esq<=esq_fim) { | ||
+ | |||
+ | aux[aux_pos]=vetor[esq]; | ||
+ | esq=esq+1; | ||
+ | aux_pos=aux_pos+1; | ||
+ | } | ||
+ | |||
+ | while (meio<=dire) { | ||
+ | |||
+ | aux[aux_pos]=vetor[meio]; | ||
+ | meio=meio+1; | ||
+ | aux_pos=aux_pos+1; | ||
+ | } | ||
+ | |||
+ | for (i=0;i<num_elementos;i++) { | ||
+ | |||
+ | vetor[dire]=aux[dire]; | ||
+ | dire=dire-1; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void m_sort(int vetor[],int aux[],int esq,int dire) { | ||
+ | |||
+ | int meio; | ||
+ | if (dire>esq) { | ||
+ | meio=(dire+esq)/ 2; | ||
+ | m_sort(vetor,aux,esq,meio); | ||
+ | m_sort(vetor,aux,meio+1,dire); | ||
+ | merge(vetor,aux,esq,meio+1,dire); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </pre> | ||
+ | |||
+ | == Referências == | ||
+ | *Site da Wikipedia em inglês: http://en.wikipedia.org/wiki/Merge_sort | ||
+ | *M. BEDER, Delano - ''Algoritmos de Ordenação: Merge Sort'': http://www.ic.unicamp.br/~luciano/ACH2002/notasdeaula/11-mergeSort.pdf | ||
+ | *FEOFILOFF, Paulo - ''Merge Sort'': http://www.ime.usp.br/~pf/mac0122-2002/aulas/mergesort.html | ||
+ | |||
+ | == Ligações Externas == | ||
+ | Demonstração de funcionamento interativa do Merge Sort (em inglês): | ||
+ | http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/mergeSort/mergeSort.html |
Edição atual tal como 22h06min de 1 de dezembro de 2008
Ordenação por intercalação (Merge Sort) é um algoritmo de ordenação muito utilizado em computação, criado pelo matemático húngaro John von Neumann (1903-1957).
Tabela de conteúdo |
Princípio de Funcionamento
O princípio básico de funcionamento do Merge Sort é simples e intuitivo: o algoritmo divide a lista a ser ordenada em várias sublistas, sempre em duas partes, até que as listas restantes contenham apenas um elemento. Após esta divisão o algoritmo faz o caminho inverso, ou seja, ele começa a "remontar" o vetor, porém ordenando os elementos (que estão em menor número) enquanto os vetores maiores são recriados.
Características
- O Merge Sort necessita de um vetor auxiliar para funcionar, de tamanho igual ao do vetor a ser ordenado, o que constitui uma desvantagem deste algoritmo.
- Sua complexidade é nlog2n (pior caso), sendo n o número de elementos que serão ordenados.
- O Merge Sort é considerado como o melhor algoritmo de ordenação já inventado, devido à sua simplicidade e eficiência.
- Alto consumo de memoria, devido à série de chamadas recursivas.
- Por ser mais complexo que os outros algoritmos de ordenação, ele só é realmente mais rápido na prática quando n for suficientemente grande.
Exemplo
Segue abaixo um exemplo de aplicação do Merge Sort para ordenar um vetor de 8 elementos:
15 99 52 14 50 64 20 77
Divisão em duas partes:
15 99 52 14 - 50 64 20 77
Divisão da primeira parte em duas outras partes:
15 99 - 52 14
Análise do primeiro par:
15- 99
Como 15 é menor do que 99, a ordem é mantida.
Análise do segundo par:
52 -14
Como 52 é maior do que 14, a ordem é invertida:
14 -52
Agora restam dois pares ordenados:
15 99 - 14 52
O algoritmo agora compara o menor valor de cada um dos dois vetores:
15 -14
Como 14 é menor do que 15, esse valor será o primeiro da lista de 4 elementos:
14 X X X
Compara-se 15 com o outro elemento do segundo vetor. Como 15 é menor do que 52, 15 ocupará a segunda posição:
14 15 X X
Agora simplesmente comparam-se os dois elementos restantes. 99 é maior do que 52, logo 52 ocupará a terceira posição, e 99 a quarta posição neste vetor de 4 elementos:
14 15 52 99
O processo é repetido de forma idêntica para a outra primeira metade do vetor inicial, que apresentará a seguinte configuração:
20 50 64 77
Neste ponto tem-se dois vetores ordenados:
14 15 52 99 - 20 50 64 77
O próximo e último passo é fazer a fusão destes dois vetores, de forma similar àquela já feita, comparando o menor elemento de cada um dos dois vetores e posicionando o menor elemento ordenadamente na lista original.
Feito este processo, o resultado final será:
14 15 20 50 52 64 77 99
Implementação em C:
void mergeSort(int vetor[],int aux[],int tam) { m_sort(vetor,aux,0,tam-1); } void merge(int vetor[],int aux[],int esq,int meio,int dire) { int i,esq_fim,num_elementos,aux_pos; esq_fim=meio-1; aux_pos=esq; num_elementos=dire-esq+1; while ((esq<=esq_fim)&&(meio<=dire)) { if (vetor[esq]<=vetor[meio]) { aux[aux_pos]=vetor[esq]; aux_pos=aux_pos+1; esq=esq+1; } else { aux[aux_pos]=vetor[meio]; aux_pos=aux_pos + 1; meio=meio+1; } } while (esq<=esq_fim) { aux[aux_pos]=vetor[esq]; esq=esq+1; aux_pos=aux_pos+1; } while (meio<=dire) { aux[aux_pos]=vetor[meio]; meio=meio+1; aux_pos=aux_pos+1; } for (i=0;i<num_elementos;i++) { vetor[dire]=aux[dire]; dire=dire-1; } } void m_sort(int vetor[],int aux[],int esq,int dire) { int meio; if (dire>esq) { meio=(dire+esq)/ 2; m_sort(vetor,aux,esq,meio); m_sort(vetor,aux,meio+1,dire); merge(vetor,aux,esq,meio+1,dire); } }
Referências
- Site da Wikipedia em inglês: http://en.wikipedia.org/wiki/Merge_sort
- M. BEDER, Delano - Algoritmos de Ordenação: Merge Sort: http://www.ic.unicamp.br/~luciano/ACH2002/notasdeaula/11-mergeSort.pdf
- FEOFILOFF, Paulo - Merge Sort: http://www.ime.usp.br/~pf/mac0122-2002/aulas/mergesort.html
Ligações Externas
Demonstração de funcionamento interativa do Merge Sort (em inglês): http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sortingII/mergeSort/mergeSort.html