Merge classificar em Java explicou

Uma lista ou matriz cuja indexação (contagem) começa de zero pode ser reduzida pela metade. A questão é que, quando o número total de elementos da lista é estranho, qual é a metade esquerda e qual é a metade certa. Quando o número total de elementos é par, não há problema. Se a duração da lista for 8, digamos, a metade esquerda terá os 4 primeiros elementos, e a metade certa tem os próximos 4 elementos. Se a duração da lista for 5, digamos, o que é estranho, então por convenção, a metade esquerda tem os 3 primeiros elementos, e a metade certa tem os próximos 2 elementos.

Se o comprimento da lista for 8, o índice para o elemento médio (médio) é considerado 3, ou seja, o quarto elemento - a contagem de índice começa de 0. Portanto, quando o comprimento da lista é uniforme, o índice para o elemento médio é de comprimento / 2 - 1.

Se o comprimento da lista for 5, o índice para o elemento médio será considerado 2, que é o terceiro elemento. Portanto, quando o comprimento da lista é ímpar, o índice para o elemento médio é de comprimento / 2 - 1/2.

Não é difícil obter o índice intermediário de uma lista com Java! - Basta usar aritmética inteira. A expressão para o índice médio é:

HighestIndex / 2

Portanto, se o comprimento for 8, o índice mais alto, que é 7, é dividido por 2 para dar 3 e um 1/2. A aritmética inteira descarta a metade, deixando você com 3, que é, comprimento / 2 - 1.

Se o comprimento for 5, o índice mais alto, que é 4, é dividido por 2 para dar 2, que é, comprimento / 2 - 1/2.

Merge Sort é um algoritmo de classificação. Neste tutorial, a classificação resultará em uma lista final, do menos ao maior valor. Merge Sort usa o paradigma de divisão e conquista. O restante deste tutorial explica que, como se aplica a Java.

Conteúdo do artigo

• Divida e conquista para a mesma classificação
• O principal método de recursão
• O método conquista ()
• Matriz temporária para o método conquista ()
• Conclusão

Divida e conquista para a mesma classificação

Divida significa dividir a lista não classificada em duas metades, como explicado acima. Em seguida, divida cada uma das metades em mais duas metades. Continue dividindo as metades resultantes até que haja n listas de um elemento cada, onde n é o comprimento da lista original.

Conquer significa começar a emparelhar listas consecutivas em uma lista enquanto classifica a lista resultante. O emparelhamento continua até que uma lista final classificada de comprimentos que seja igual ao comprimento original seja obtida.

Considere a lista não classificada de cartas alfabéticas:

M k q c e t g

A duração desta lista é 7. O diagrama a seguir ilustra como a classificação de mesclagem desta lista é feita em teoria:

Do diagrama, a divisão para valores únicos leva 3 etapas. A conquista, que está se fundindo e classificando, dá mais três etapas para ter a lista final classificada.

Se um programador escrever 6 segmentos de código para conseguir isso? - Não. O programador precisa ter um esquema de recursão usando uma lista temporária.

A propósito, observe que G parece bastante estranho em seu posicionamento para a divisão da primeira metade direita. Isso ocorre porque o comprimento da lista é um número ímpar, 7. Se o comprimento fosse um número par, digamos 6, Q teria parecido tão estranho de maneira semelhante para a divisão da primeira metade esquerda.

O restante deste artigo explica "Merge Sort in Java", usando a lista não classificada:

M k q c e t g

O principal método de recursão

Existem três métodos neste programa. Os métodos são, o método divide (), o método conquer () e o método principal (). O método divide () é o principal método. Ele se chama repetidamente para as metades esquerda e direita e chama o método Conquer () no final de seu corpo. O código para o método principal é:

dividir void (char arr [], int Beg, int end)
int mid;
se (implorar < end)
MID = (BEG + END)/2;
divida (arr, implorar, meados);
divida (arr, meados+1, extremidade);
conquista (arr, implorar, meio, fim);

No início, leva a matriz dada, o índice de matriz inicial (Beg), que é 0, e o índice de matriz final, que é 6. O método não será executado se não tiver pelo menos dois elementos. A verificação é feita pela Condição IF: “Se (implorar < end)”. The first divide() recall calls the left half of the list, and the second divide() recall calls the right to half of the list.

Assim, para a primeira execução ou passagem, do método Divide (), a condição IF é satisfeita (mais de um elemento). O índice médio é 3 = (0 + 6) / 2 (aritmética inteira). As três chamadas de método e sua ordem com seus argumentos se tornam:

divida (arr, 0, 3);
divida (arr, 4, 6);
conquista (arr, 0, 3, 6);

Existem três chamadas aqui. O primeiro dessas chamadas, chama o método Divide () novamente para a metade esquerda da lista. Os dois segundos métodos são observados e reservados em sua ordem, a serem executados mais tarde. A segunda chamada divide () chamaria o método divide () para a metade direita da lista. O método conquistador executaria as duas primeiras metades juntas.

Antes da segunda passagem do método Divide (), a lista deve ser considerada dividida em dois da seguinte maneira:

M k q c e t g

Na segunda passagem do método Divide (), a metade esquerda da lista é atendida. A chamada para a segunda passagem é:

divida (arr, 0, 3);

Desta vez, o índice médio é, 1 = (0 + 3) / 2 (aritmética inteira). O método chama, sua ordem e argumentos se tornam,

divida (arr, 0, 1);
divida (arr, 2, 3);
conquista (arr, 0, 1, 3);

Observe que o novo índice final é 3, que é o fim da primeira metade à esquerda. O primeiro dessas chamadas, chama o método Divide () novamente para a metade esquerda da primeira metade esquerda da lista. Os segundos dois métodos são observados e reservados em sua ordem, a serem executados mais tarde, com seus novos argumentos. A segunda chamada divide () ligaria para o método divide () para a metade direita da primeira metade esquerda da lista. O método conquista () executaria as duas novas metades.

Antes da terceira passagem do método Divide (), a lista deve ser considerada dividida da seguinte forma:

M k q c e t g

A terceira passagem do método de divisão é a chamada:

divida (arr, 0, 1);

Nesta terceira passagem do método Divide (), a metade esquerda da nova sub-lista em questão é atendida. Desta vez, o índice médio é, 0 = (0 + 1) / 2 (aritmética inteira). O método chama, sua ordem e argumentos se tornam,

divida (arr, 0, 0);
divida (arr, 1, 1);
conquista (arr, 0, 0, 1);

Observe que o novo índice final é 1, que é o fim da nova metade esquerda. A primeira dessas chamadas é,

divida (arr, 0, 0);

Falha por causa da condição if, “se (implorar < end)” - beg, and end are the same, meaning there is only one element. The second divide() method,

divida (arr, 1, 1);

Também falha por um motivo semelhante. Neste ponto, a lista deve ser considerada dividida como,

M k q c e t g

A terceira chamada é:

conquista (arr, 0, 0, 1);

A chamada conquistadora para as duas sub-listas é M e K, cada uma consistindo em um elemento. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria k m. A lista inteira se tornaria:

K m q c e t g

Lembre -se de que existem métodos, que foram observados e reservados. Eles seriam chamados em ordem inversa, agora com,

divida (arr, 2, 3);

Esta é a quarta passagem do método Divide (). É para lidar com a sub-lista, Q C, cujo índice de partida é 2 e o índice final é 3. O índice médio é agora 2 = (2 + 3) / 2 (aritmética inteira). O método chama, sua ordem e argumentos se tornam,

divida (arr, 2, 2);
divida (arr, 3, 3);
conquista (arr, 2, 2, 3);

O quinto passe do método Divide () é a chamada,

divida (arr, 2, 2);

Observe que o índice de início e final é o mesmo, o que significa que há apenas um elemento. Esta chamada falha, por causa da condição if, “se (implorar < end)”. The second divide() call,

divida (arr, 3, 3);

Também falha pelo mesmo motivo. Neste ponto, a lista deve ser considerada dividida como,

K m q c e t g

A terceira chamada no passe do método é:

conquista (arr, 2, 2, 3);

A chamada conquista para as duas sub-listas é Q e C, cada uma consistindo em um elemento. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria C q. A lista inteira se tornaria:

K m C q e t g

Lembre -se de que ainda existem métodos que foram observados e reservados. Eles continuariam a ser chamados na ordem inversa; agora com,

divida (arr, 4, 6);

Esta é a sexta passagem do método Divide (). É para lidar com a sub-lista, e t g, cujo índice de partida é 4 e o índice final é 6. O índice médio é agora 5 = (4 + 6) / 2 (aritmética inteira). O método chama, sua ordem e argumentos se tornam,

divida (arr, 4, 5);
divida (arr, 5, 6);
conquista (arr, 4, 5, 6);

O sétimo passe do método Divide () é a chamada,

divida (arr, 4, 5);

As duas duas chamadas são anotadas e reservadas. Observe que o novo índice final é 5, que é o fim da nova metade esquerda. O índice médio agora é 4 = (4 + 5) / 2 (aritmética inteira). O método chama, sua ordem e argumentos se tornam,

divida (arr, 4, 4);
divida (arr, 5, 5);
conquista (arr, 4, 4, 5);

A oitava passagem é:

divida (arr, 4, 4);

Observe que o índice de início e final é o mesmo, o que significa que há apenas um elemento. Esta chamada falha, por causa da condição if, “se (implorar < end)”. The second divide() method call is,

divida (arr, 5, 5);

Que também falha pelo mesmo motivo. Neste ponto, a lista deve ser considerada dividida como,

K m C q e t g

A terceira chamada é:

conquista (arr, 4, 4, 5);

É a chamada conquistadora para as duas sub-listas: E e T: a primeira sub-lista que consiste em um elemento, e a segunda sub-lista que consiste em um elemento. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria e g . A lista inteira se tornaria:

K m q c e t g

Embora a sequência e t permaneça a mesma, observe que a classificação está ocorrendo, embora o tipo final ainda esteja por vir.

Lembre -se de que ainda existem métodos que foram observados e reservados. Eles são chamados em ordem inversa. Eles agora serão chamados começando com,

divida (arr, 5, 6);

Observe que o novo índice final é 6, que é o fim da nova metade direita. O índice médio é agora 5 = (5 + 6) / 2 (aritmética inteira). O método chama, sua ordem e argumentos se tornam,

divida (arr, 5, 5);
divida (arr, 6, 6);
conquista (arr, 5, 5, 6);

As duas primeiras chamadas falham porque estão abordando sub-listas de elementos únicos. Neste ponto, toda a lista é:

K m q c e t g

A próxima chamada é:

conquista (arr, 5, 5, 6);

É a chamada conquistadora para as duas sub-listas: T e G: a primeira sub-lista que consiste em um elemento, e a segunda sub-lista que consiste em um elemento. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria GT . A lista inteira se tornaria:

K m q c e g t

Lembre -se de que ainda existem métodos que foram observados e reservados. Eles são chamados em ordem inversa. O próximo a ser chamado é,

conquista (arr, 0, 1, 3);

É a chamada conquistadora para as duas sub-listas: km e q c: a primeira sub-lista que consiste em dois elementos, e a segunda sub-lista que consiste em dois elementos. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria C K m q. A lista inteira se tornaria:

C k m q e g t

Outro método conquista () que foi observado e reservado é:

conquista (arr, 4, 5, 6);

É o conquista que chama as duas sub-listas: e g e t. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria e g t. A lista inteira se tornaria:

C k m q e g t

A última chamada conquista () observada e reservada é:

conquista (arr, 0, 3, 6);

É a chamada conquistadora para as duas sub-listas: c k m q e e g t: a primeira sub-lista que consiste em quatro elementos, e a segunda sub-lista que consiste em três elementos. O método conquista () mescla e classifica duas sub-listas. A sub-lista resultante seria C e g k m q t, que é a sub-lista inteira, isto é:

C e g k m q t

E isso termina a fusão e classificação.

O método conquista ()

O método conquistador mescla e classifica duas sub-listas. Uma sub-lista consiste em pelo menos um valor. O método conquistador toma como argumento, a matriz original, o índice de início da primeira sub-lista, o índice médio das duas sub-listas consecutivas vistas juntas e o índice final da segunda sub-lista. O método conquistador tem uma matriz temporária, cuja duração é a da matriz original. O código para o método conquistador é:

Void Conquer (Char arr [], int Beg, int Mid, int end)
int i = BEG, J = MID+1, K = BEM, INDEX = BEM;
char temp [] = novo char [7];
enquanto eu<=mid && j<=end)
se (arr [i]temp [index] = arr [i];
i = i+1;

outro
temp [index] = arr [j];
j = j+1;

índice ++;

if (i> Mid)
enquanto (j<=end)
temp [index] = arr [j];
índice ++;
j ++;


outro
enquanto eu<=mid)
temp [index] = arr [i];
índice ++;
i ++;


k = BEM;
enquanto (karr [k] = temp [k];
k ++;

O principal método é:

public static void main (string [] args)
char arr [] = 'm', 'k', 'q', 'c', 'e', ​​'t', 'g';
Theclass mescort = new theClass ();
mesclar.divida (arr, 0,6);
Sistema.fora.println ("Os elementos classificados:");
para (int i = 0; i<7;i++)
Sistema.fora.impressão (arr [i]); Sistema.fora.imprimir(");

Sistema.fora.println ();

O método Divide (), o método conquista () e o método principal () devem ser combinados em uma classe. A saída é:

C e g k m q t

Como esperado.

Matriz temporária para o método conquista ()

À medida que os pares da sub-lista são classificados, o resultado é mantido na matriz temporária, temp []. O arranjo de valores na matriz temporária acaba substituindo o conteúdo da matriz original. A seguir, mostra o arranjo na matriz original e a da matriz temporária para as diferentes chamadas do método conquista ():

conquista (arr, 0, 0, 1);
arr [7]: m k q c e t g
Temp [7]: K M - - - - -
conquista (arr, 2, 2, 3);
arr [7]: K m q c e t g
Temp [7]: K M C q - - -
conquista (arr, 4, 4, 5);
arr [7]: K M C Q E T G
Temp [7]: K M C Q E T -
conquista (arr, 5, 5, 6);
arr [7]: K M C Q E T G
Temp [7]: K M C q E g t
conquista (arr, 0, 1, 3);
arr [7]: K M C q E g t
Temp [7]: C K M Q E G T
conquista (arr, 4, 5, 6);
arr [7]: c k m q e g t
Temp [7]: C K M Q E G T
conquista (arr, 0, 3, 6);
arr [7]: c k m q e g t
Temp [7]: c e g k m q t

Conclusão

Merge Sort é um esquema de classificação que usa o paradigma de divisão e conquista. Ele divide uma lista de elementos em elementos únicos e depois começa a reunir pares consecutivos de sub-listas, classificados, começando pelas sub-listas de elemento único. Os procedimentos de divisão e conquista são feitos juntos. Este tutorial explicou como é feito em java.

Chrys