Unisci l'ordinamento in Java spiegato

Un elenco o un array il cui indicizzazione (conteggio) inizia da zero può essere dimezzato. La domanda è: quando il numero totale di elementi nell'elenco è dispari, qual è la metà sinistra e qual è la metà destra. Quando il numero totale di elementi è pari, non c'è problema. Se la lunghezza dell'elenco è 8, diciamo, allora la metà sinistra ha i primi 4 elementi e la metà destra ha i successivi 4 elementi. Se la lunghezza dell'elenco è 5, diciamo, il che è strano, quindi per convenzione, la metà sinistra ha i primi 3 elementi e la metà destra ha i successivi 2 elementi.

Se la lunghezza dell'elenco è 8, allora l'indice per l'elemento medio (medio) è considerato 3, che è, il 4 ° elemento - il conteggio dell'indice inizia da 0. Quindi, quando la lunghezza dell'elenco è uniforme, l'indice per l'elemento medio è la lunghezza / 2 - 1.

Se la lunghezza dell'elenco è 5, allora l'indice per l'elemento medio è considerato 2, che è il terzo elemento. Quindi, quando la lunghezza dell'elenco è dispari, l'indice per l'elemento medio è lunghezza / 2 - 1/2.

Non è difficile ottenere il medio indice di un elenco con Java! - Basta usare aritmetico intero. L'espressione per l'indice medio è:

HighSestIndex / 2

Quindi, se la lunghezza è 8, l'indice più alto, che è 7, è diviso per 2 per dare 3 e 1/2. L'aritmetica intero scarta la metà, lasciandoti con 3, che è, lunghezza / 2 - 1.

Se la lunghezza è 5, l'indice più alto, che è 4, è diviso per 2 per dare 2, che è, lunghezza / 2 - 1/2.

L'ordinamento di unione è un algoritmo di smistamento. In questo tutorial, l'ordinamento si tradurrà in un elenco finale, dal minimo al massimo valore. Merge Ordin usa il paradigma di divisione e conquista. Il resto di questo tutorial spiega che, come si applica a Java.

Contenuto dell'articolo

• Dividi e conquista per l'ordinamento di unione
• Il metodo di ricorsione principale
• Il metodo Conquer ()
• Array temporaneo per il metodo Conquer ()
• Conclusione

Dividi e conquista per l'ordinamento di unione

Dividi significa dividere l'elenco non desiderato in due metà, come spiegato sopra. Quindi dividi ciascuna delle metà in altre due metà. Continua a dividere le metà risultanti fino a quando non ci sono n elenchi di un elemento ciascuno, dove n è la lunghezza dell'elenco originale.

Conquer significa iniziare ad abbinare elenchi consecutivi in ​​un elenco durante l'ordinamento dell'elenco risultante. L'abbinamento continua fino a quando si ottiene un elenco ordinato finale di lunghezze uguale alla lunghezza originale.

Prendi in considerazione l'elenco non desiderato di lettere alfabetiche:

M K Q C E T G

La lunghezza di questo elenco è 7. Il seguente diagramma illustra come in teoria viene eseguita il punto di fusione di questo elenco:

Dal diagramma, la divisione ai valori singoli richiede 3 passaggi. La conquista, che si sta unendo e ordinando, fa altri 3 passaggi per avere l'elenco finale ordinato.

Se un programmatore dovesse scrivere 6 segmenti di codice per raggiungere questo obiettivo? - NO. Il programmatore deve avere uno schema di ricorsione utilizzando un elenco temporaneo.

A proposito, nota che G sembra piuttosto strano nel suo posizionamento per la divisione della prima metà destra. Questo perché la lunghezza dell'elenco è un numero dispari, 7. Se la lunghezza fosse un numero pari, diciamo 6, Q sarebbe apparso in modo dispari in modo simile per la divisione della prima metà sinistra.

Il resto di questo articolo spiega "Urdine di unione in Java", utilizzando l'elenco non desiderato:

M K Q C E T G

Il metodo di ricorsione principale

Ci sono tre metodi in questo programma. I metodi sono, il metodo Divide (), il metodo Conquer () e il metodo principale (). Il metodo Divide () è il metodo principale. Si chiama ripetutamente per le metà sinistra e destra e chiama il metodo Conquer () alla fine del suo corpo. Il codice per il metodo principale è:

void divide (char arr [], int beg, int end)
int a metà;
Se (Beg < end)
mid = (beg + end)/2;
dividere (arr, beg, metà);
dividere (arr, metà+1, fine);
conquista (arr, beg, metà, fine);

All'inizio, prende l'array dato, l'indice di array iniziale (Beg), che è 0, e l'indice dell'array finale, che è 6. Il metodo non eseguirà se non ha almeno due elementi. L'assegno viene eseguito dall'if-condizione, “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.

Quindi, per la prima esecuzione o pass, del metodo Divide (), la condizione if è soddisfatta (più di un elemento). L'indice medio è 3 = (0 + 6) / 2 (aritmetico intero). Le tre chiamate del metodo e il loro ordine con i loro argomenti diventano:

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

Ci sono tre chiamate qui. Il primo di queste chiamate, chiama di nuovo il metodo Divide () per la metà sinistra dell'elenco. I secondi due metodi sono annotati e riservati nel loro ordine, da eseguire in seguito. La seconda chiamata di divide () chiamerebbe il metodo Divide () per la metà destra dell'elenco. Il metodo Conquer eseguirà insieme le due prime metà.

Prima del secondo passaggio del metodo Divide (), l'elenco dovrebbe essere considerato diviso in due come segue:

M K Q C E T G

Nel secondo passaggio del metodo Divide (), è seguita la metà sinistra dell'elenco. La chiamata per il secondo passaggio è:

dividere (arr, 0, 3);

Questa volta, l'indice medio è, 1 = (0 + 3) / 2 (aritmetico intero). Il metodo chiama, il loro ordine e gli argomenti diventano,

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

Si noti che il nuovo indice di end è 3, che è la fine della prima metà sinistra. Il primo di queste chiamate, chiama di nuovo il metodo Divide () per la metà sinistra della prima metà sinistra dell'elenco. I secondi due metodi sono annotati e riservati nel loro ordine, da eseguire in seguito, con i loro nuovi argomenti. La seconda chiamata di divide () chiamerebbe il metodo Divide () per la metà destra della prima metà sinistra dell'elenco. Il metodo Conquer () eseguirà le due nuove metà.

Prima del terzo passaggio del metodo Divide (), l'elenco dovrebbe essere considerato diviso come segue:

M K Q C E T G

Il terzo passaggio del metodo Divide è la chiamata:

dividere (arr, 0, 1);

In questo terzo passaggio del metodo Divide (), è seguita la metà sinistra della nuova sotto-list in questione. Questa volta, l'indice medio è, 0 = (0 + 1) / 2 (intero aritmetico). Il metodo chiama, il loro ordine e gli argomenti diventano,

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

Si noti che il nuovo indice finale è 1, che è la fine della nuova metà sinistra. La prima di queste chiamate è,

dividere (arr, 0, 0);

Fallisce a causa della condizione if, “if (beg < end)” - beg, and end are the same, meaning there is only one element. The second divide() method,

dividere (arr, 1, 1);

Fallisce anche per un motivo simile. A questo punto, l'elenco dovrebbe essere considerato diviso come,

M K Q C E T G

La terza chiamata è:

conquista (arr, 0, 0, 1);

La conquista della conquista per i due sotto-list è M e K, ognuno composto da un elemento. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe k m. L'intero elenco diventerebbe:

K m q c e t g

Ricorda che ci sono metodi, che sono stati annotati e riservati. Sarebbero chiamati in ordine inverso, ora con,

dividere (arr, 2, 3);

Questo è il quarto passaggio del metodo Divide (). È gestire la sotto-list, Q c, il cui indice iniziale è 2 e l'indice finale è 3. L'indice medio è ora 2 = (2 + 3) / 2 (aritmetico intero). Il metodo chiama, il loro ordine e gli argomenti diventano,

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

Il quinto passaggio del metodo Divide () è la chiamata,

dividere (arr, 2, 2);

Si noti che l'indice di inizio e fine è lo stesso, il che significa che esiste un solo elemento. Questa chiamata fallisce, a causa dell'if-condizione, “If (Beg < end)”. The second divide() call,

dividere (arr, 3, 3);

Fallisce anche per lo stesso motivo. A questo punto, l'elenco dovrebbe essere considerato diviso come,

K m q c e t g

La terza chiamata nel passaggio del metodo è:

conquista (arr, 2, 2, 3);

La conquista della conquista per le due sotto-liste è Q e C, ognuna composta da un elemento. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe C q. L'intero elenco diventerebbe:

K m c q e t g

Ricorda che ci sono ancora metodi, che sono stati annotati e riservati. Continuerebbero a essere chiamati in ordine inverso; ora con,

dividere (arr, 4, 6);

Questo è il sesto passaggio del metodo Divide (). È per gestire la sotto-list, e t g, il cui indice iniziale è 4 e l'indice finale è 6. L'indice medio è ora 5 = (4 + 6) / 2 (aritmetico intero). Il metodo chiama, il loro ordine e gli argomenti diventano,

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

Il settimo passaggio del metodo Divide () è la chiamata,

dividere (arr, 4, 5);

Le seconde due chiamate sono annotate e riservate. Si noti che il nuovo indice di fine è 5, che è la fine della nuova metà sinistra. L'indice medio è ora 4 = (4 + 5) / 2 (aritmetico intero). Il metodo chiama, il loro ordine e gli argomenti diventano,

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

L'ottavo passaggio è:

dividere (arr, 4, 4);

Si noti che l'indice di inizio e fine è lo stesso, il che significa che esiste un solo elemento. Questa chiamata fallisce, a causa dell'if-condizione, “If (Beg < end)”. The second divide() method call is,

dividere (arr, 5, 5);

Che fallisce anche per lo stesso motivo. A questo punto, l'elenco dovrebbe essere considerato diviso come,

K m c q e t g

La terza chiamata è:

conquista (arr, 4, 4, 5);

È la richiesta di conquista per i due sotto-listi: E e T: il primo sotto-elenco costituito da un elemento e la seconda sotto-elenco costituita da un elemento. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe e g . L'intero elenco diventerebbe:

K m q c e t g

Sebbene la sequenza di E t rimanga la stessa, nota che è avvenuto l'ordinamento, anche se il tipo finale deve ancora venire.

Ricorda che ci sono ancora metodi che sono stati annotati e riservati. Sono chiamati in ordine inverso. Ora saranno chiamati a partire da,

dividere (arr, 5, 6);

Si noti che il nuovo indice di end è 6, che è la fine della nuova metà destra. L'indice medio è ora 5 = (5 + 6) / 2 (aritmetico intero). Il metodo chiama, il loro ordine e gli argomenti diventano,

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

Le prime due chiamate falliscono perché stanno affrontando i sotto-listi a elemento singolo. A questo punto, l'intero elenco è:

K m q c e t g

La prossima chiamata è:

conquista (arr, 5, 5, 6);

È la richiesta di conquista per i due sotto-listi: T e G: il primo sotto-elenco costituito da un elemento e la seconda sotto-elenco costituita da un elemento. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe g t . L'intero elenco diventerebbe:

K m q c e g t

Ricorda che ci sono ancora metodi che sono stati annotati e riservati. Sono chiamati in ordine inverso. Il prossimo da chiamare è,

conquista (arr, 0, 1, 3);

È la richiesta di conquista per i due sotto-listi: K M e Q C: il primo sotto-list composto da due elementi e la seconda sotto-list costituita da due elementi. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe C K M Q. L'intero elenco diventerebbe:

C k m q e g t

Un altro metodo Conquer () che è stato notato e riservato è:

conquista (arr, 4, 5, 6);

È la richiesta di conquista per i due sotto-listi: e g e t. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe e g t. L'intero elenco diventerebbe:

C k m q e g t

L'ultima chiamata conquer () indicata e riservata è:

conquista (arr, 0, 3, 6);

È la richiesta di conquista per i due sotto-listi: C K M Q ed E G T: la prima sotto-list composta da quattro elementi e la seconda sotto-list composta da tre elementi. Il metodo Conquer () si fonde e ordina due sotto-listi. La sotto-elenco risultante sarebbe c e g k m q t, che è l'intera sotto-list, cioè:

C e g k m q t

E questo termina la fusione e l'ordinamento.

Il metodo Conquer ()

Il metodo Conquer si fonde e ordina due secondari. Un sotto-list è costituito da almeno un valore. Il metodo Conquer prende come argomento, l'array originale, l'indice iniziale della prima sotto-list, l'indice medio dei due sotto-listi consecutivi visti insieme e l'indice finale della seconda sotto-list. Il metodo Conquer ha un array temporaneo, la cui lunghezza è quella dell'array originale. Il codice per il metodo Conquer è:

void conquer (char arr [], int beg, int mid, int end)
int i = beg, j = mid+1, k = beg, indice = beg;
char temp [] = new char [7];
mentre io<=mid && j<=end)
if (arr [i]temp [indice] = arr [i];
i = i+1;

altro
temp [indice] = arr [j];
j = j+1;

indice ++;

if (i> mid)
mentre (j<=end)
temp [indice] = arr [j];
indice ++;
J ++;


altro
mentre io<=mid)
temp [indice] = arr [i];
indice ++;
I ++;


k = beg;
mentre (karr [k] = temp [k];
K ++;

Il metodo principale è:

public static void main (string [] args)
char arr [] = 'm', 'k', 'q', 'c', 'e', ​​'t', 'g';
TheClass Mergesort = new theClass ();
Mergesort.dividere (arr, 0,6);
Sistema.fuori.println ("Gli elementi ordinati:");
per (int i = 0; i<7;i++)
Sistema.fuori.print (arr [i]); Sistema.fuori.stampa(");

Sistema.fuori.println ();

Il metodo Divide (), il metodo Conquer () e il metodo principale () devono essere combinati in una classe. L'output è:

C e g k m q t

Come previsto.

Array temporaneo per il metodo Conquer ()

Man mano che le coppie di sotto-list vengono ordinate, il risultato è trattenuto nell'array temporaneo, temp []. La disposizione dei valori nell'array temporanea alla fine sostituisce il contenuto dell'array originale. Quanto segue mostra la disposizione nell'array originale e quella dell'array temporaneo per le diverse chiamate del metodo Conquer ():

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

Conclusione

Unisci un sistema di smistamento che utilizza il paradigma di divisione e conquista. Divide un elenco di elementi in singoli elementi e quindi inizia a riunire coppie consecutive di sotto-list, ordinati, a partire dai sotto-listi a singolo elemento. Le procedure di divisione e conquista vengono eseguite insieme in modo ricorsivo. Questo tutorial ha spiegato come viene fatto in Java.

Chrys