Ordenação por Intercalação
Ddrv utfpr (disc | contribs) |
Ddrv utfpr (disc | contribs) |
||
| Linha 18: | Linha 18: | ||
15 99 52 14 50 64 20 77 | 15 99 52 14 50 64 20 77 | ||
| + | |||
Divisão em duas partes: | Divisão em duas partes: | ||
| − | 15 99 52 14 | + | |
| + | 15 99 52 14 - 50 64 20 77 | ||
| + | |||
Divisão da primeira parte em duas outras partes: | Divisão da primeira parte em duas outras partes: | ||
| − | 15 99 | + | |
| + | 15 99 - 52 14 | ||
| + | |||
Análise do primeiro par: | Análise do primeiro par: | ||
| − | 15 99 | + | |
| + | 15- 99 | ||
| + | |||
Como 15 é menor do que 99, a ordem é mantida. | Como 15 é menor do que 99, a ordem é mantida. | ||
| + | |||
Análise do segundo par: | Análise do segundo par: | ||
| − | 52 14 | + | |
| + | 52 -14 | ||
| + | |||
Como 52 é menor do que 14, a ordem é invertida: | Como 52 é menor do que 14, a ordem é invertida: | ||
| − | 14 52 | + | |
| + | 14 -52 | ||
| + | |||
Agora restam dois pares ordenados: | Agora restam dois pares ordenados: | ||
| − | 15 99 | + | |
| + | 15 99 - 14 52 | ||
| + | |||
O algoritmo agora compara o menor valor de cada um dos dois vetores: | O algoritmo agora compara o menor valor de cada um dos dois vetores: | ||
| − | 15 14 | + | |
| + | 15 -14 | ||
| + | |||
Como 14 é menor do que 15, esse valor será o primeiro da lista de 4 elementos: | Como 14 é menor do que 15, esse valor será o primeiro da lista de 4 elementos: | ||
| + | |||
14 X X X | 14 X X X | ||
| + | |||
Compara-se 15 com o outro elemento do segundo vetor. Como 15 é menor do que 52, 15 ocupará segunda posição: | Compara-se 15 com o outro elemento do segundo vetor. Como 15 é menor do que 52, 15 ocupará segunda posição: | ||
| + | |||
14 15 X X | 14 15 X X | ||
| + | |||
Agora simplesmente compara-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: | Agora simplesmente compara-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 | 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: | 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 | 20 50 64 77 | ||
| + | |||
Neste ponto tem-se dois vetores ordenados: | Neste ponto tem-se dois vetores ordenados: | ||
| + | |||
14 15 52 99 - 20 50 64 77 | 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. | 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á: | Feito este processo, o resultado final será: | ||
| + | |||
14 15 20 50 52 64 77 99 | 14 15 20 50 52 64 77 99 | ||
Edição de 20h44min de 28 de novembro 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).
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 o 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 é n<math>log[2]</math>n, 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.
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 é menor 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á segunda posição:
14 15 X X
Agora simplesmente compara-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
