Merge sort é um dos algoritmos básicos da ciência da computação, formulado em 1945 pelo grande matemático John von Neumann. Enquanto participava do Projeto Manhattan, Neumann se deparou com a necessidade de processar com eficiência enormes quantidades de dados. O método que ele desenvolveu usava o princípio de "dividir e conquistar", o que reduzia significativamente o tempo necessário para o trabalho.
Princípio e uso do algoritmo
O método merge sort é usado em problemas de ordenação de estruturas que têm acesso ordenado a elementos, como arrays, listas, streams.
Durante o processamento, o bloco de dados inicial é dividido em pequenos componentes, até um elemento, que na verdade já é uma lista ordenada. Em seguida, ele é remontado na ordem correta.
Ordenar um array de um determinado tamanho requer uma área de memória adicional do mesmo tamanho, na qual o array ordenado é coletado em partes.
O método pode ser usado para ordenar qualquer tipo de dados comparável, como números ou strings.
Mesclar ordenadoparcelas
Para entender o algoritmo, vamos começar sua análise do final - do mecanismo de mesclagem de blocos ordenados.
Vamos imaginar que temos dois arrays de números ordenados de alguma forma que precisam ser combinados entre si para que a ordenação não seja quebrada. Para simplificar, classificaremos os números em ordem crescente.
Exemplo elementar: ambos os arrays consistem em um elemento cada.
int arr1={31}; int arr2={18};
Para juntá-los, você precisa pegar o elemento zero do primeiro array (não esqueça que a numeração começa do zero) e o elemento zero do segundo array. São, respectivamente, 31 e 18. De acordo com a condição de ordenação, o número 18 deve vir primeiro, pois é menor. Basta colocar os números na ordem correta:
int resultado={18, 31};
Vamos ver um exemplo mais complicado, onde cada array consiste em vários elementos:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
O algoritmo de mesclagem consistirá em comparar sequencialmente elementos menores e colocá-los no array resultante na ordem correta. Para acompanhar os índices atuais, vamos introduzir duas variáveis - index1 e index2. Inicialmente, definimos como zero, pois os arrays estão ordenados e os menores elementos estão no início.
int index1=0; int index2=0;
Vamos escrever todo o processo de fusão passo a passo:
- Pegue o elemento com index1 do array arr1, e o elemento com index2 do array arr2.
- Compare, selecione o menor deles e coloquematriz resultante.
- Incrementa o índice atual do elemento menor em 1.
- Continue do primeiro passo.
Na primeira órbita, a situação ficará assim:
index1=0; índice2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; índice1++; resultado[0]=arr1[0]; // resultado=[2]
No segundo turno:
index1=1; índice2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; índice2++; resultado[1]=arr2[0]; // resultado=[2, 5]
Terceiro:
index1=1; índice2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; índice2++; resultado[2]=arr2[1]; // resultado=[2, 5, 6]
E assim por diante, até que o resultado seja um array completamente ordenado: {2, 5, 6, 17, 21, 19, 30, 45}.
Certas dificuldades podem surgir se arrays com tamanhos diferentes forem mesclados. E se um dos índices atuais atingir o último elemento e ainda houver membros restantes no segundo array?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 passo index1=0, index2=0; 1 2 resultado={1, 2}; // 3 passos index1=1, index2=1; 4 < 5 resultado={1, 2, 4}; //4 passos index1=2, index2=1 ??
A variável index1 atingiu o valor 2, mas o array arr1 não possui um elemento com esse índice. Tudo é simples aqui: basta transferir os elementos restantes do segundo array para o resultante, preservando sua ordem.
resultado={1, 2, 4, 5, 6, 7, 9};
Esta situação nos indica a necessidadecorresponda o índice de verificação atual com o comprimento da matriz que está sendo mesclada.
Esquema de mesclagem para sequências ordenadas (A e B) de diferentes comprimentos:
- Se o comprimento de ambas as sequências for maior que 0, compare A[0] e B[0] e mova a menor para o buffer.
- Se o comprimento de uma das sequências for 0, pegue os elementos restantes da segunda sequência e, sem alterar sua ordem, mova para o final do buffer.
Implementação da segunda etapa
Um exemplo de junção de dois arrays ordenados em Java é dado abaixo.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.comprimento + a2.comprimento]; int i=0, j=0; for (int k=0; k a1.comprimento-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.comprimento-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Aqui:
- a1 e a2 são os arrays ordenados originais a serem mesclados;
- a3 – array final;
- i e j são índices de elementos atuais para arrays a1 e a2.
A primeira e a segunda condição if garantem que os índices não ultrapassem o tamanho do array. O terceiro e quarto blocos de condição, respectivamente, são movidos para a matriz resultante do elemento menor.
Divida e Conquiste
Então, aprendemos a mesclar oscoleções de valores. Pode-se dizer que a segunda parte do algoritmo de ordenação por mesclagem - a própria mesclagem - já foi ordenada.
No entanto, você ainda precisa entender como ir do array original não ordenado de números para vários ordenados que podem ser mesclados.
Vamos considerar o primeiro estágio do algoritmo e aprender a separar arrays.
Isso não é difícil - a lista original de valores é dividida ao meio, então cada parte também é bifurcada, e assim por diante até que blocos muito pequenos sejam obtidos.
O comprimento de tais elementos mínimos pode ser igual a um, ou seja, eles podem ser um array ordenado, mas isso não é uma condição necessária. O tamanho do bloco é determinado antecipadamente, e qualquer algoritmo de ordenação adequado que funcione eficientemente com arrays de tamanhos pequenos (por exemplo, quicksort ou insert sort) pode ser usado para ordená-lo.
Parece assim.
// matriz original {34, 95, 10, 2, 102, 70}; // primeira divisão {34, 95, 10} e {2, 102, 70}; // segunda divisão {34} e {95, 10} e {2} e {102, 70}
Os blocos resultantes, consistindo de 1-2 elementos, são muito fáceis de organizar.
Depois disso, você precisa mesclar os pequenos arrays já ordenados em pares, preservando a ordem dos membros, o que já aprendemos a fazer.
Implementação da primeira etapa
O particionamento recursivo de um array é mostrado abaixo.
void mergeSort(T a, início longo, fim longo) { long split; E se(início < fim) { divisão=(início + fim)/2; mergeSort(a, iniciar, dividir); mergeSort(a, split+1, final); mesclar(a, iniciar, dividir, terminar); } }
O que acontece neste código:
-
A função mergeSort obtém o array inicial
a
e as bordas esquerda e direita da região a ser classificada (índices start e
- finish).
-
Se o comprimento desta seção for maior que um (
start < finish
), então ela é dividida em duas partes (pelo índice
- split), e cada um é classificado recursivamente.
-
Na chamada de função recursiva para o lado esquerdo, o índice inicial do gráfico e o índice
split
são passados. Para a direita, respectivamente, o início será
- (split + 1), e o final será o último índice da seção original.
-
Função
merge
obtém duas sequências ordenadas (
a[start]…a[split]
e
- a[split +1]…a[finish]) e os mescla na ordem de classificação.
A mecânica da função de mesclagem é discutida acima.
Esquema geral do algoritmo
O método merge sort array consiste em duas grandes etapas:
- Divida o array original não classificado em pedaços pequenos.
- Recolha-os em pares, seguindo a regra de ordenação.
Uma tarefa grande e complexa é dividida em muitas tarefas simples, que são resolvidas sequencialmente, levando ao resultado desejado.
Avaliação do método
A complexidade de tempo da ordenação por mesclagem é determinada pela altura da árvore divididaalgoritmo e é igual ao número de elementos no array (n) vezes seu logaritmo (log n). Tal estimativa é chamada logarítmica.
Esta é uma vantagem e uma desvantagem do método. Seu tempo de execução não muda mesmo no pior caso, quando o array original é ordenado em ordem inversa. No entanto, ao processar dados completamente ordenados, o algoritmo não fornece ganho de tempo.
Também é importante observar o custo de memória do método de ordenação por mesclagem. Eles são iguais ao tamanho da coleção original. Nesta área adicionalmente alocada, um array ordenado é montado a partir das peças.
Implementação do algoritmo
Pascal merge sort é mostrado abaixo.
Procedure MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: inteiro; f1, f2: texto; b: booleano Begincol:=0; Atribuir(f, nome); reset(f); Enquanto não EOF(f) comece read(f, a1); inc(co); fim; fechar(f); Assign(f1, '{nome do 1º arquivo auxiliar}'); Assign(f2, '{nome do 2º arquivo auxiliar}'); s:=1; Enquanto (s<kol) inicia Reset(f); reescrever(f1); reescrever(f2); Para i:=1 para kol div 2 comece Read(f, a1); escreva(f1, a1, ' '); fim; Se (kol div 2) mod s0 então comece tmp:=kol div 2; Enquanto tmp mod s0 começa Read(f, a1); escreva(f1, a1, ' '); inc(tmp); fim; fim; Enquanto não EOF(f) comece Read(f, a2); escreva(f2, a2, ' '); fim; fechar(f); fechar(f1); fechar(f2); reescrever(f); reset(f1); reset(f2); Leia(f1, a1); Leia(f2, a2); Enquanto (não EOF(f1)) e (não EOF(f2)) começam i:=0; j:=0; b:=verdadeiro; Enquanto (b) e (não EOF(f1)) e (não EOF(f2)) começam Se (a1<a2) então começaescreva(f, a1, ' '); Leia(f1, a1); inc(i); End else begin Write(f, a2, ' '); Leia(f2, a2); inc(j); fim; Se (i=s) ou (j=s) então b:=false; fim; Se não b então comece While (i<s) e (não EOF(f1)) comece Write(f, a1, ' '); Leia(f1, a1); inc(i); fim; Enquanto (j<s) e (não EOF(f2)) começam Write(f, a2, ' '); Leia(f2, a2); inc(j); fim; fim; fim; Embora não EOF(f1) comece tmp:=a1; Leia(f1, a1); Se não for EOF(f1) então Write(f, tmp, ' ') else Write(f, tmp); fim; Enquanto não EOF(f2) comece tmp:=a2; Leia(f2, a2); Se não for EOF(f2) então Write(f, tmp, ' ') else Write(f, tmp); fim; fechar(f); fechar(f1); fechar(f2); s:=s2; fim; Apagar(f1); Apagar(f2); Fim;
Visualmente, a operação do algoritmo se parece com isso (topo - seqüência não ordenada, inferior - ordenado).
Classificação de dados externos
Muitas vezes há a necessidade de ordenar alguns dados localizados na memória externa do computador. Em alguns casos, eles são de tamanho impressionante e não podem ser colocados na RAM para facilitar o acesso a eles. Para esses casos, métodos de classificação externos são usados.
A necessidade de acessar mídia externa degrada a eficiência do tempo de processamento.
A complexidade do trabalho é que o algoritmo só pode acessar um elemento do fluxo de dados por vez. E neste caso, um dos melhores resultados é mostrado pelo método merge sort, que pode comparar os elementos de dois arquivos sequencialmente um após o outro.
Lendo dados defonte externa, seu processamento e escrita no arquivo final são realizados em blocos ordenados (séries). De acordo com a forma de trabalhar com o tamanho das séries ordenadas, existem dois tipos de ordenação: mesclagem simples e natural.
Mescla simples
Com uma simples mesclagem, o comprimento da série é fixo.
Assim, no arquivo original não classificado, todas as séries consistem em um elemento. Após a primeira etapa, o tamanho aumenta para dois. Próximo - 4, 8, 16 e assim por diante.
Funciona assim:
- O arquivo fonte (f) é dividido em dois auxiliares - f1, f2.
- Eles são novamente mesclados em um arquivo (f), mas ao mesmo tempo todos os elementos são comparados em pares e formam pares. O tamanho da série nesta etapa se torna dois.
- O passo 1 é repetido.
- O passo 2 é repetido, mas os 2s já ordenados são mesclados para formar 4s ordenados.
- O loop continua, aumentando a série em cada iteração, até que todo o arquivo seja ordenado.
Como você sabe que a classificação externa com uma mesclagem simples está completa?
- novo comprimento da série (após a fusão) não inferior ao número total de elementos;
- apenas um episódio restante;
- Arquivo auxiliar f2 foi deixado vazio.
As desvantagens de uma mesclagem simples são: como a duração da execução é fixa em cada passagem de mesclagem, os dados parcialmente ordenados levarão tanto tempo para serem processados como dados completamente aleatórios.
Fusão Natural
Este método não limita o comprimentosérie, mas escolhe o máximo possível.
Algoritmo de ordenação:
- Ler a sequência inicial do arquivo f. O primeiro elemento recebido é escrito no arquivo f1.
- Se a próxima entrada satisfizer a condição de ordenação, ela é escrita lá, se não, então para o segundo arquivo auxiliar f2.
- Desta forma, todos os registros do arquivo fonte são distribuídos, e uma sequência ordenada é formada em f1, que determina o tamanho atual da série.
- Os arquivos f1 e f2 são mesclados.
- O ciclo se repete.
Devido ao tamanho não fixo da série, é necessário marcar o final da sequência com um caractere especial. Portanto, ao mesclar, o número de comparações aumenta. Além disso, o tamanho de um dos arquivos auxiliares pode ser próximo ao tamanho do original.
Em média, a mesclagem natural é mais eficiente do que a mesclagem simples com ordenação externa.
Recursos do algoritmo
Ao comparar dois valores idênticos, o método preserva sua ordem original, ou seja, é estável.
O processo de classificação pode ser dividido com muito sucesso em vários segmentos.
O vídeo demonstra claramente a operação do algoritmo de ordenação por mesclagem.
