Ordenação por Intercalação
Ddrv utfpr (disc | contribs) |
Ddrv utfpr (disc | contribs) |
||
| 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). | 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: == | == 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. | 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: == | == Características: == | ||
Edição de 21h26min 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 é nlog(2)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.
