Fusionar ordenar en Java explicado

Una lista o una matriz cuya indexación (conteo) comienza desde cero se puede reducir a la mitad. La pregunta es, cuando el número total de elementos en la lista es extraño, cuál es la mitad izquierda y cuál es la mitad derecha. Cuando el número total de elementos es par, no hay problema. Si la longitud de la lista es 8, digamos, entonces la mitad izquierda tiene los primeros 4 elementos, y la mitad derecha tiene los siguientes 4 elementos. Si la longitud de la lista es 5, digamos, lo cual es extraño, entonces por convención, la mitad izquierda tiene los primeros 3 elementos, y la mitad derecha tiene los siguientes 2 elementos.

Si la longitud de la lista es 8, entonces el índice para el elemento medio (medio) se considera 3, que es, el cuarto elemento - Contado de índice comienza a partir de 0. Entonces, cuando la longitud de la lista es uniforme, el índice para el elemento medio es longitud / 2 - 1.

Si la longitud de la lista es 5, entonces el índice para el elemento medio se considera 2, que es el tercer elemento. Entonces, cuando la longitud de la lista es impar, el índice para el elemento medio es longitud / 2 - 1/2.

No es difícil obtener el índice medio de una lista con Java! - Solo usa aritmética entera. La expresión para el índice medio es:

HighestIdex / 2

Entonces, si la longitud es 8, el índice más alto, que es 7, se divide por 2 para dar 3 y un 1/2. La aritmética entera descarta la mitad, dejándote con 3, que es, longitud / 2 - 1.

Si la longitud es 5, el índice más alto, que es 4, se divide por 2 para dar 2, que es, longitud / 2 - 1/2.

Fusion Sort es un algoritmo de clasificación. En este tutorial, la clasificación dará como resultado una lista final, desde el menor valor hasta el mayor valor. Fusion Sort usa el paradigma de división y conquistar. El resto de este tutorial explica que, como se aplica a Java.

Contenido del artículo

• Dividir y conquistar para fusionar
• El método de recursión principal
• El método conquer ()
• Matriz temporal para el método conquer ()
• Conclusión

Dividir y conquistar para fusionar

Divide significa dividir la lista sin clasificar en dos mitades, como se explicó anteriormente. Luego divida cada una de las mitades en dos mitades más. Sigue dividiendo las mitades resultantes hasta que haya n listas de un elemento cada una, donde n es la longitud de la lista original.

Conquer significa comenzar a emparejar listas consecutivas en una lista mientras se clasifica la lista resultante. El emparejamiento continúa hasta que se obtiene una lista final ordenada de longitudes que es igual a la longitud original.

Considere la lista no organizada de letras alfabéticas:

M K Q C E T G

La duración de esta lista es 7. El siguiente diagrama ilustra cómo se realiza la clasificación fusionada de esta lista en teoría:

Desde el diagrama, la división a los valores individuales toma 3 pasos. El conquistador, que se está fusionando y la clasificación, toma otros 3 pasos para tener la lista final ordenada.

Si un programador escribe 6 segmentos de código para lograr esto? - No. El programador debe tener un esquema de recursión utilizando una lista temporal.

Por cierto, observe que G se ve bastante extraño en su posicionamiento para la división de la primera mitad derecha. Esto se debe a que la longitud de la lista es un número impar, 7. Si la longitud fuera un número uniforme, digamos 6, Q habría parecido extraño de manera similar a la división de la primera mitad izquierda.

El resto de este artículo explica "Merge Sort in Java", utilizando la lista sin clasificar:

M K Q C E T G

El método de recursión principal

Hay tres métodos en este programa. Los métodos son, el método divide (), el método conquer () y el método main (). El método Divide () es el método principal. Se llama repetidamente a las mitades izquierda y derecha y llama al método conquer () al final de su cuerpo. El código para el método principal es:

void divide (char arr [], int beg, int end)
int Mid;
Si (ruega < end)
Mid = (Beg + End)/2;
divide (arr, beg, medio);
divide (arr, mediano+1, final);
conquistar (arr, beg, mediano, final);

Al principio, se toma la matriz dada, el índice de matriz inicial (Beg), que es 0, y el índice de matriz final, que es 6. El método no se ejecutará si no tiene al menos dos elementos. El cheque se realiza por la condición if, "if (beg < 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.

Entonces, para la primera ejecución o pase, del método divide (), la condición if se satisface (más de un elemento). El índice medio es 3 = (0 + 6) / 2 (aritmética entera). Las tres llamadas del método y su orden con sus argumentos se convierten en:

divide (arr, 0, 3);
divide (arr, 4, 6);
conquistar (arr, 0, 3, 6);

Hay tres llamadas aquí. La primera de estas llamadas, llama nuevamente el método Divide () para la mitad izquierda de la lista. Los segundos dos métodos se observan y reservan en su orden, para ser ejecutados más tarde. La segunda llamada Divide () llamaría al método Divide () para la mitad correcta de la lista. El método de conquistar ejecutaría las dos primeras mitades juntas.

Antes del segundo pase del método Divide (), la lista debe considerarse dividida en dos de la siguiente manera:

M K Q C E T G

En el segundo pase del método Divide (), la mitad izquierda de la lista se atiende a. La llamada para el segundo pase es:

divide (arr, 0, 3);

Esta vez, el índice medio es, 1 = (0 + 3) / 2 (aritmética entera). El método llama, su orden y argumentos se convierten,

divide (arr, 0, 1);
divide (arr, 2, 3);
conquistar (arr, 0, 1, 3);

Tenga en cuenta que el nuevo índice final es 3, que es el final de la primera mitad izquierda. La primera de estas llamadas, llama nuevamente el método Divide () para la mitad izquierda de la primera mitad izquierda de la lista. Los segundos dos métodos se anotan y reservan en su orden, para ser ejecutados más tarde, con sus nuevos argumentos. La segunda llamada Divide () llamaría al método Divide () para la mitad derecha de la primera mitad izquierda de la lista. El método conquer () ejecutaría las dos nuevas mitades.

Antes del tercer pase del método Divide (), la lista debe considerarse dividida de la siguiente manera:

M K Q C E T G

El tercer pase del método de división es la llamada:

divide (arr, 0, 1);

En este tercer pase del método Divide (), la mitad izquierda de la nueva subsist en cuestión se atiende a. Esta vez, el índice medio es, 0 = (0 + 1) / 2 (aritmética entera). El método llama, su orden y argumentos se convierten,

divide (arr, 0, 0);
divide (arr, 1, 1);
conquistar (arr, 0, 0, 1);

Tenga en cuenta que el nuevo índice final es 1, que es el final de la nueva mitad izquierda. La primera de estas llamadas es,

divide (arr, 0, 0);

Falla debido a la condición if, "if (beg < end)” - beg, and end are the same, meaning there is only one element. The second divide() method,

divide (arr, 1, 1);

También falla por una razón similar. En este punto, la lista debe considerarse dividida como,

M K Q C E T G

La tercera llamada es:

conquistar (arr, 0, 0, 1);

El llamado de conquistar para las dos subsists es M y K, cada una consta de un elemento. El método conquer () se fusiona y clasifica dos subsistentes. La subsist resultante sería k m. Toda la lista se convertiría en:

K M Q C E T G

Recuerde que hay métodos, que se observaron y reservaron. Serían llamados en orden inverso, ahora con,

divide (arr, 2, 3);

Este es el cuarto pase del método Divide (). Es para manejar la subsist, Q C, cuyo índice inicial es 2 y el índice final es 3. El índice medio ahora es 2 = (2 + 3) / 2 (aritmética entera). El método llama, su orden y argumentos se convierten,

divide (arr, 2, 2);
divide (arr, 3, 3);
conquistar (arr, 2, 2, 3);

El quinto pase del método divide () es la llamada,

divide (arr, 2, 2);

Tenga en cuenta que el índice inicial y final son los mismos, lo que significa que solo hay un elemento. Esta llamada falla, debido a la condición de IF, "si (bends < end)”. The second divide() call,

divide (arr, 3, 3);

También falla por la misma razón. En este punto, la lista debe considerarse dividida como,

K M Q C E T G

La tercera llamada en el Método Pase es:

conquistar (arr, 2, 2, 3);

El llamado de conquistar para las dos subsists es Q y C, cada una consta de un elemento. El método conquer () se fusiona y clasifica dos subsistentes. La subsist resultante sería C Q. Toda la lista se convertiría en:

K M C Q E T G

Recuerde que todavía hay métodos, que se observaron y se reservaron. Seguirían llamando en orden inverso; ahora con,

divide (arr, 4, 6);

Este es el sexto pase del método divide (). Es para manejar la subsist, e t g, cuyo índice inicial es 4 y el índice final es 6. El índice medio ahora es 5 = (4 + 6) / 2 (aritmética entera). El método llama, su orden y argumentos se convierten,

divide (arr, 4, 5);
divide (arr, 5, 6);
conquistar (arr, 4, 5, 6);

El séptimo pase del método divide () es la llamada,

divide (arr, 4, 5);

Las segundas dos llamadas se anotan y reservan. Tenga en cuenta que el nuevo índice final es 5, que es el final de la nueva mitad izquierda. El índice medio ahora es 4 = (4 + 5) / 2 (aritmética entera). El método llama, su orden y argumentos se convierten,

divide (arr, 4, 4);
divide (arr, 5, 5);
conquistar (arr, 4, 4, 5);

El octavo pase es:

divide (arr, 4, 4);

Tenga en cuenta que el índice inicial y final son los mismos, lo que significa que solo hay un elemento. Esta llamada falla, debido a la condición de IF, "si (bends < end)”. The second divide() method call is,

divide (arr, 5, 5);

Que también falla por la misma razón. En este punto, la lista debe considerarse dividida como,

K M C Q E T G

La tercera llamada es:

conquistar (arr, 4, 4, 5);

Es la llamada de conquistar para las dos subsistes: E y T: la primera subsist que consta de un elemento, y la segunda subsist que consta de un elemento. El método conquer () se fusiona y clasifica dos subsistentes. La subsist resultante sería e g . Toda la lista se convertiría en:

K M Q C E T G

Aunque la secuencia de E T sigue siendo la misma, observe que se ha llevado a cabo la clasificación, aunque el tipo final aún está por llegar.

Recuerde que todavía hay métodos que se observaron y se reservaron. Se llaman en orden inverso. Ahora serán llamados comenzando con,

divide (arr, 5, 6);

Tenga en cuenta que el nuevo índice final es 6, que es el final de la nueva mitad derecha. El índice medio ahora es 5 = (5 + 6) / 2 (aritmética entera). El método llama, su orden y argumentos se convierten,

divide (arr, 5, 5);
divide (arr, 6, 6);
conquistar (arr, 5, 5, 6);

Las dos primeras llamadas fallan porque están abordando las sub-listas de elementos de un solo elemento. En este punto, toda la lista es:

K M Q C E T G

La siguiente llamada es:

conquistar (arr, 5, 5, 6);

Es la llamada de conquistar para las dos subsistes: T y G: la primera subsist que consta de un elemento, y la segunda subsistencia que consta de un elemento. El método conquer () se fusiona y clasifica dos subsistentes. La subsist resultante sería g t . Toda la lista se convertiría en:

K M Q C E G T

Recuerde que todavía hay métodos que se observaron y se reservaron. Se llaman en orden inverso. El siguiente a llamar es,

conquistar (arr, 0, 1, 3);

Es el llamado de conquistar para las dos subsists: K M y Q C: La primera subsist que consta de dos elementos, y la segunda subsist que consta de dos elementos. El método conquer () se fusiona y clasifica dos subsistentes. La subsist resultante sería c k m q. Toda la lista se convertiría en:

C K M Q E G T

Otro método conquer () que se observó y reservó es:

conquistar (arr, 4, 5, 6);

Es la llamada de conquistar para las dos subsistes: E G y T. El método conquer () se fusiona y clasifica dos subsistentes. La subsist resultante sería e g t. Toda la lista se convertiría en:

C K M Q E G T

La última llamada conquistar () observada y reservada es:

conquistar (arr, 0, 3, 6);

Es el llamado de conquistar para las dos subsistes: C k m q y e g t: la primera subsist que consta de cuatro elementos, y la segunda sublista que consta de tres elementos. El método conquer () se fusiona y clasifica dos subsistentes. La subplave resultante sería C E G K M Q T, que es toda la subsist, es decir:

C E G K M Q T

Y eso termina la fusión y la clasificación.

El método conquer ()

El método de conquistar fusiona y clasifica dos subsists. Una subsist consta de al menos un valor. El método de conquista toma como argumento, la matriz original, el índice inicial de la primera subsist, el índice medio de las dos subsists consecutivas vistas juntas, y el índice final de la segunda subsist. El método conquistador tiene una matriz temporal, cuya longitud es la de la matriz original. El código para el método de conquistación es:

void conquer (char arr [], int beg, int mid, int end)
int i = beg, j = mid+1, k = beg, index = beg;
char temp [] = nuevo char [7];
mientras yo<=mid && j<=end)
if (arr [i]temp [index] = arr [i];
i = i+1;

demás
temp [index] = arr [j];
j = j+1;

índice ++;

if (i> mid)
mientras (J<=end)
temp [index] = arr [j];
índice ++;
j ++;


demás
mientras yo<=mid)
temp [index] = arr [i];
índice ++;
i ++;


k = suplicar;
mientras (karr [k] = temp [k];
K ++;

El método principal es:

public static void main (string [] args)
char arr [] = 'm', 'k', 'q', 'c', 'e', ​​'t', 'g';
THECLASS Mergesort = new THECLASS ();
merger.divide (arr, 0,6);
Sistema.afuera.println ("Los elementos ordenados:");
para (int i = 0; i<7;i++)
Sistema.afuera.imprimir (arr [i]); Sistema.afuera.imprimir(");

Sistema.afuera.println ();

El método Divide (), el método conquer () y el método Main () debe combinarse en una clase. La salida es:

C E G K M Q T

Como se esperaba.

Matriz temporal para el método conquer ()

A medida que se clasifican los pares de la subproducción, el resultado se mantiene en la matriz temporal, temp []. La disposición de los valores en la matriz temporal reemplaza el contenido de la matriz original. A continuación se muestra la disposición en la matriz original y la de la matriz temporal para las diferentes llamadas del método conquer ():

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

Conclusión

Merge Sort es un esquema de clasificación que usa el paradigma de división y conquistar. Divide una lista de elementos en elementos individuales y luego comienza a unir pares consecutivos de subsists, ordenadas, comenzando desde las sub-listas de elementos individuales. Los procedimientos de división y conquista se realizan juntos recursivamente. Este tutorial ha explicado cómo se hace en Java.

Chrys