Ordenação por Intercalação

De Wiki DAINF
(Diferença entre revisões)
(→Características)
 
(22 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).
 
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 os vetores maiores são recriados.
  
−
== Características: ==
+
== 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.
+
* 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</math>n, sendo n o número de elementos que serão ordenados.
+
* 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.
+
* 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 23h06min 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

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

Obtida de "http://dainf.ct.utfpr.edu.br/wiki/index.php?title=Ordena%C3%A7%C3%A3o_por_Intercala%C3%A7%C3%A3o&oldid=875"
Ferramentas pessoais