Wiki DAINF - Contribuições do usuário [pt-br]

Ordenação por Intercalação

2008-12-02T01:06:30Z

Ddrv utfpr: /* Características */

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 é 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: ==

<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

Ordenação por Intercalação

2008-12-02T01:03:57Z

Ddrv utfpr: /* Referências */

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 é nlog2n, 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 a 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

Ordenação por Intercalação

2008-12-02T01:01:07Z

Ddrv utfpr: /* Ligações Externas */

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 é nlog2n, 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 a 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

== 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

Ordenação por Intercalação

2008-12-02T01:00:44Z

Ddrv utfpr: /* Referências */

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 é nlog2n, 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 a 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

== 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

Ordenação por Intercalação

2008-12-02T00:59:44Z

Ddrv utfpr: /* Referências */

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 é nlog2n, 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 a 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

== 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

Ordenação por Intercalação

2008-12-02T00:47:48Z

Ddrv utfpr:

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 é nlog2n, 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 a 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 ==

== 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

Ordenação por Intercalação

2008-11-30T21:05:22Z

Ddrv utfpr: /* Características: */

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 é nlog2n, 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 a 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>

Ordenação por Intercalação

2008-11-30T21:05:05Z

Ddrv utfpr: /* Características: */

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 é n log2 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.

* Alto consumo de memoria, devido a 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>

Ordenação por Intercalação

2008-11-30T21:04:27Z

Ddrv utfpr: /* Características: */

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 é (n log 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.

* Alto consumo de memoria, devido a 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>

Ordenação por Intercalação

2008-11-29T22:38:13Z

Ddrv utfpr:

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 é 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.

* Alto consumo de memoria, devido a 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>

Ordenação por Intercalação

2008-11-29T22:33:08Z

Ddrv utfpr:

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 é 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.

- Alto consumo de memoria, devido a 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>

Ordenação por Intercalação

2008-11-29T02:50:05Z

Ddrv utfpr: /* Características: */

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 é 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.

- Alto consumo de memoria, devido a 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á 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>

Ordenação por Intercalação

2008-11-29T02:46:06Z

Ddrv utfpr: /* Características: */

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 é 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.

- O Merge Sort é um algoritmo recursivo.

- 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á 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>

Ordenação por Intercalação

2008-11-29T02:23:57Z

Ddrv utfpr:

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 é 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 é 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á 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>

Ordenação por Intercalação

2008-11-29T02:20:02Z

Ddrv utfpr:

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 é 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 é 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á 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);
}
}
}

Ordenação por Intercalação

2008-11-29T00:09:34Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:45:29Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:44:54Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:44:31Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:43:03Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:30:32Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:30:16Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:28:31Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:28:19Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:27:24Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:26:22Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:26:10Z

Ddrv utfpr:

Ordenação por Intercalação

2008-11-28T23:25:26Z

Ddrv utfpr:

Ordenação por intercalação (Merge Sort) é um algoritmo de ordenação muito utilizado em computação, criado pelo matemático 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.

Ordenação por Intercalação

2008-11-28T22:43:52Z

Ddrv utfpr:

Teste... :#