Mesclar classificar em c
O programa de Mergesort, escrito normalmente, é comparável (em termos de velocidade) com a função Sort () fornecida por C ++ em sua biblioteca de algoritmo. Merge-Sort também é um programa comercial de uso geral.
Este artigo explica como escrever o programa de fusão no idioma C.
Dividir e conquistar o algoritmo, em seu sentido amplo
Em seu sentido amplo, a variedade de elementos é dividida em duas metades: a metade esquerda e a metade direita. Se o número total de elementos a serem classificados for estranho, a metade esquerda será maior que a metade direita, por 1 unidade. Caso contrário, ambas as metades têm o mesmo comprimento. As duas metades são então mescladas durante a classificação para formar uma matriz classificada. A fusão/classificação é conquistando. Considere os seguintes caracteres a serem classificados:
Q W E R T Y U I O PDividir este conjunto de caracteres alfabéticos em duas metades, dá:
Q W E R T Y U I O PUma sub -matriz é chamada de corrida. Então, a sub -matriz esquerda, "Q w e r t" é uma corrida e a sub -matriz certa, "y u i o p" também é uma corrida. Uma corrida também pode ter apenas um elemento.
Fusão/classificação (conquista) Ambas as metades em um conjunto fornece:
E i o p q r t u w yO código a ser dividido por 2 é:
int Imiddle = (ibegin + iEnd) / 2;Esta é a divisão inteira. Então, todo o número parte do resultado é tomado. Com isso, se o número total de elementos no conjunto for ímpar, a metade esquerda seria maior que a metade direita, por 1 unidade para indexação baseada em zero.
Para a afirmação acima e o conjunto, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', ibegin = 0, iEnd = 10 (que é o último índice de 9, mais 1), imiddle = 5;
O código para mesclar/classificar (conquista) é:
int i = ibegin;int j = imiddle;
para (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
outro
Q [k] = p [j];
j = j + 1;
P é a matriz dada. Q teria a matriz classificada, neste caso.
Se este código for aplicado ao conjunto, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p' , haverá fusão das metades divididas, mas nenhuma classificação (porque cada elemento na corrida esquerda é menor que 'y'). Este código é revisado abaixo para mostrar sua eficácia na classificação de um par consecutivo de corridas.
Algoritmo prático de divisão e conquista
Todo o programa de mesclagem pode ser escrito de cima para baixo ou de baixo para cima. Neste artigo, o programa está escrito, de cima para baixo.
Um mesclar opera conceitualmente da seguinte maneira:
1) Divida o conjunto não classificado em n subconjuntos (execuções), onde cada um tem um elemento. Observe que um conjunto com apenas um elemento é considerado classificado.
2) mesclar repetidamente subconjuntos para obter novos subconjuntos classificados, até que apenas um subconjunto seja deixado. Este é o conjunto classificado.
Com esses dois pontos, um determinado conjunto não classificado é dividido em duas corridas. Cada uma dessas duas execuções é registrada na memória para mesclar/classificar juntos, mas ainda não mesclada ou classificada. Cada corrida novamente de ambos os lados é dividido em dois. Os pares consecutivos de corridas são gravados para mesclar/classificar juntos, mas ainda não mesclados ou classificados. Esta divisão em dois e gravação para fusão/classificação de pares consecutivos são repetidos até que haja apenas um elemento por execução.
A gravação na memória para a fusão/classificação de corridas consecutivas é feita chamando o código de classificação acima de forma recursiva após a divisão. O código de classificação está em uma função separada. A declaração de divisão e a chamada da função de classificação (que também faz a fusão) estão em um segmento de código (uma função) com a declaração de divisão digitada primeiro.
Quando a divisão atingiu o estado de um único elemento, as funções de fusão/classificação registradas na memória são chamadas em ordem inversa em que foram gravadas. É uma função de mesclagem/classificação que foi registrada na memória muitas vezes com argumentos diferentes. Pares consecutivos de elementos únicos são classificados pela primeira vez, mesclando ao mesmo tempo. A classificação e fusão de corridas consecutivas continuam até que todo o conjunto seja classificado. Então, a classificação não está realmente no arranjo de elementos, como foi dado originalmente.
Em C, há uma necessidade de uma segunda matriz, cuja duração é tão longa quanto a matriz fornecida. Inicialmente, todos os elementos para esta segunda matriz devem ser feitos, o valor padrão do tipo de dados. Os elementos da matriz dada são classificados nesta segunda matriz. Em seguida, copiou de volta para a matriz dada, substituindo os elementos não classificados.
Para os caracteres, esta segunda matriz pode ser criada e inicializada da seguinte maneira:
char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';int sz = sizeof (p)/sizeof (p [0]);
Char Q [SZ];
para (int i = 0; i
Aqui, a matriz dada é P, e a segunda matriz é q. Este código pode estar na função principal. Em C/C ++, o caractere padrão é "e não é um espaço ("). No entanto, como o compilador G ++ não permitiria a atribuição de "para q [i], o espaço único ("), foi atribuído.
Observe que os valores padrão para os elementos da matriz Q não são realmente necessários para o programa completo de Mergesort, pois ainda serão substituídos pelos elementos de interesse. Declarando a matriz q com seu tamanho, a SZ é suficiente.
O conjunto, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', é usado para explicar como Murgesort é alcançado praticamente nesta seção. Dando os valores padrão da matriz Q foi ensinada neste artigo como conhecimento extra.
O conjunto é dividido nos dois conjuntos:
'Q', 'w', 'e', 'r', 't' e 'y', 'u', 'i', 'o', 'p'O código de fusão/classificação acima é chamado de função, mas a classificação e a fusão não ocorrem. No programa real, a classificação e fusão dessas duas corridas são registradas na memória, primeiro. A classificação e a fusão não serão necessariamente necessariamente feitas nesses dois arranjos específicos de personagens.
Os dois subconjuntos acima são cada um, mais divididos em dois para ter:
'Q', 'w', 'e' e 'r', 't' e 'y', 'u', 'i' e 'o', 'p'Observe que para cada nova divisão aqui, o subconjunto esquerdo é mais longo que o subconjunto direito por uma unidade.
O código de mesclagem/classificação acima é chamado de função, para pares consecutivos desses novos subconjuntos. Mas classificar e fusão não ocorre imediatamente. A classificação e fusão desses pares consecutivos de corridas são registrados na memória do computador. A classificação e a fusão não serão, em última análise.
Os subconjuntos acima são cada um, mais divididos em dois para ter:
'Q', 'w' e 'e' e 'r' e 't' e 'y', 'u' e 'i' e 'o' e 'P'A classificação e fusão de pares consecutivos é registrada.
Aqui, alguns subconjuntos não podem ser mais divididos porque cada um deles consiste em um elemento. Então, a divisão dos subconjuntos de mais de um comprimento acima, leva a:
'Q' e 'w' e 'e' e 'r' e 't' e 'y' e 'u' e 'i' e ' O ' e ' P 'A classificação e fusão de pares consecutivos é registrada.
A função de classificação e fusão é codificada de maneira recursiva. E assim, será chamado na ordem invertida, para muitas vezes, foi registrado.
Então, 'q' e 'w' serão classificados e mesclados em 'q', 'w'. 'E' e 'r' serão classificados e mesclados em 'e', 'r'. 'T'. 'Y' será classificado e mesclado em 't', 'y'. 'U' e 'i' serão classificados e mesclados em 'i', 'u'. 'O'. 'P' será classificado e mesclado em 'O', 'P'. A função de mesclagem e classificação acima é usada aqui; e é usado por toda parte.
Próximo: 'q', 'w' e 'e', 'r' serão classificados e mesclados em 'e', 'q', 'r', 'w'. 'T', 'y' e 'i', 'u' serão classificados e fundidos em 'i', 't', 'u', 'y'. Nesta fase, 'O', 'P' não se unirá a nenhum subconjunto anterior de dois. A função de mesclagem e classificação acima foi usada aqui e é usada por toda parte.
O próximo estágio: 'e', 'q', 'r', 'w' e 'i', 't', 'u', 'y' são classificados e mesclados em 'e', ' I ',' q ',' r ',' t ',' u ',' w ',' y '. Nesta fase, 'O', 'P' novamente não se unirá a nenhum dos subconjuntos anteriores.
O último estágio: 'e', 'i', 'q', 'r', 't', 'u', 'w', 'y' e 'o', p ' são classificados e mesclados em 'e', 'i', 'o', 'p', 'q', 'r', 't', 'u', 'w', 'y'. O conjunto não classificado foi classificado.
Codificação Mersort em C
A tarefa é classificar a matriz P e não a matriz q. Então, para todo o programa de mesclagem, a matriz q é feita pela primeira vez uma cópia da matriz p. O programa então classifica a matriz q na matriz p. Isso não é exatamente o que é insinuado acima. Existem quatro funções para o programa completo de Mergesort.
A função de dividir e mesclar
Esta é a principal função no programa. Lembre -se de que a fusão também envolve a classificação das corridas consecutivas esquerda e direita. Essa fusão está na memória e realmente começa quando a matriz foi dividida por dois e dois e dois etc. Até que haja apenas um elemento por corrida. Então, classificar e fusão começam nessa fase com um par para um elemento por corrida. O esqueleto da função de classificação é:
Void TopdownsplitMerge (Char q [], int ibegin, int iend, char p [])| |
// Divida o subconjunto por mais de 1 elemento em dois
int Imiddle = (ibegin + iEnd) / 2; // Imiddle é o ponto médio
| |
| |
| |
// mescla os subconjuntos resultantes da matriz q [] em p []
TopdownMerge (Q, Ibegin, Imiddle, IEND, P);
Esta função leva a matriz fornecida como Q, que neste caso é na verdade a matriz de cópias q. Também leva a matriz de cópias como P, que neste caso é realmente a matriz dada P. Para a primeira chamada desta função, Ibegin = 0 e IEND = n, onde n é do tamanho de ambas as matrizes. Isso é por causa do emprego indexado por zero.
Após uma divisão por dois. A divisão por dois dá o número inteiro, imiddle, ignorando o restante. Este é o último índice da corrida esquerda e também o primeiro índice da corrida certa. Esta ambiguidade é eliminada pela condição enquanto se classifica o código de classificação.
A última declaração no código acima é uma chamada para a função precisa de mesclagem e classificação. Esta chamada vai para a memória, quando chamado. Ele será executado em ordem invertida para todas as suas chamadas, porque é uma chamada recursiva. Leva as variáveis como argumentos. Q, Ibegin, iEnd e P, recebidos pela função codificada externa. Imiddle, que também é um de seus argumentos, é criado dentro da função codificada externa, acima da chamada.
Está dentro desta função codificada externa que as execuções esquerda e direita devem ser identificadas (divididas). É melhor fazer isso fazendo uma chamada recursiva para a função codificada externa da seguinte maneira (algum código incluído na definição de função):
Void TopdownsplitMerge (Char q [], int ibegin, int iend, char p [])// Divida o subconjunto por mais de 1 elemento em dois
int Imiddle = (ibegin + iEnd) / 2; // Imiddle é o ponto médio
// classificar recursivamente as duas corridas da matriz A [] em B []
topdownsplitMerge (P, Ibegin, Imiddle, Q); // Divida o subconjunto esquerdo em dois para classificar, após a memorização
topdownsplitMerge (P, Imiddle, iEnd, Q); // Divida o subconjunto direito em dois para classificar, após a memorização
// mescla os subconjuntos resultantes da matriz q [] em p []
TopdownMerge (Q, Ibegin, Imiddle, IEND, P);
As duas novas chamadas recursivas foram digitadas acima do topdownMerge () Chamada recursiva. Essas duas chamadas serão memorizadas junto com o topdownmerge () e chamadas quantas vezes forem necessárias, cada uma em ordem inversa.
Se a matriz dada não tiver elemento, não deve haver classificação. Se o número de elementos na matriz dada é 1, então a matriz já está classificada e nenhuma classificação deve ocorrer. Isso é resolvido por uma declaração dentro, mas no topo da função codificada externa, TOPDOWNSPLITMERGE () da seguinte maneira:
Void TopdownsplitMerge (Char q [], int ibegin, int iend, char p [])If (iend - ibegin<= 1)
retornar;
int Imiddle = (ibegin + iEnd) / 2;
topdownsplitMerge (P, Ibegin, Imiddle, Q);
topdownsplitMerge (P, Imiddle, iEnd, Q);
TopdownMerge (Q, Ibegin, Imiddle, IEND, P);
A função precisa para mesclar e classificar
O nome desta função é TopdownMerge (). É chamado recursivamente pelo topdownsplitMerge (). O código é:
Void TopdownMerge (char p [], int ibegin, int imiddle, int iend, char q [])// Embora existam elementos nos subconjuntos esquerdo ou direito…
int i = ibegin;
int j = imiddle;
para (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
outro
Q [k] = p [j];
j = j + 1;
Em teoria, essa função itera desde o início da corrida esquerda (subconjunto) até o final da corrida direita (subconjunto). Observe como a ambiguidade mencionada acima foi atendida pela condição enquanto constitui.
Fazendo uma cópia única para todos os elementos
No início do programa, após a função abaixo (esta seção), foi chamada, todos os elementos da matriz dada devem ser copiados para a matriz, q. O código para isso é:
void copyArray (char p [], int ibegin, int iend, char q [])para (int i = ibegin; i
É chamado uma vez da seguinte função. Isso leva como argumentos, a matriz dada, P, depois 0, depois n e a outra matriz q, que está em teoria vazia, mas já tem o mesmo número de elementos que P. IEND, que é o mesmo que n, aqui é o comprimento da matriz originalmente dada.
Função para iniciar o programa
A função de iniciar o programa é:
Void TopdownMergesort (char p [], char q [], int n)copyArray (p, 0, n, q); // p [] é copiado para q [] uma vez
topdownsplitmerge (q, 0, n, p);
Ele chama a função copyArray (), com os argumentos esperados. Ele chama a seguir a função principal, TopdownsplitMerge (), com as posições das matrizes, P e Q, trocadas. É por isso que, no código TopdownMerge (), os valores classificados são enviados para Q e não para P.
Acordo de código
Se as quatro funções codificadas acima forem digitadas na seguinte ordem,
- Void TopdownMerge ()
- Void TopdownsPlitMerge ()
- copyArray ()
- TopdownMergesort ()
Em seguida, o programa de Mergesort (consistindo principalmente dessas quatro funções) funcionará em um compilador C sem nenhum problema.
C função principal
Uma função principal C adequada para este programa é:
int main (int argc, char ** argv)char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';
int sz = sizeof (p)/sizeof (p [0]);
Char Q [SZ];
para (int i = 0; i
TopdownMergesort (P, Q, SZ);
para (int i = 0; i
printf ("\ n");
retornar 0;
Conclusão
Divida e conquista o algoritmo divide o problema em pedaços menores, com a esperança de resolvê -los independentemente. Depois que todas as peças menores foram resolvidas, suas soluções são combinadas em uma solução principal. Com Merge-Sort, há divisão contínua por dois, até que cada subconjunto tenha um elemento de comprimento e automaticamente já classificado. Reunir essas corridas únicas, envolve funções recursivas e classificação real, começando com pares de elementos únicos.