Unisci l'ordinamento in C
Il programma Mergesort, scritto normalmente, è comparabile (in termini di velocità) alla funzione Sort () fornita da C ++ nella sua libreria di algoritmo. Merge-Sort è anche un programma commerciale per uso generale.
Questo articolo spiega come scrivere il programma Mergesort in lingua C.
Algoritmo di divisione e conquista, in suo ampio senso
Nel suo ampio senso, l'array di elementi è divisa in due metà: la metà sinistra e la metà destra. Se il numero totale di elementi da ordinare è dispari, la metà sinistra è resa più grande della metà destra, di 1 unità. Altrimenti, entrambe le metà sono della stessa lunghezza. Le due metà vengono quindi unite durante l'ordinamento per formare un array ordinato. La fusione/smistamento sta conquistando. Considera da ordinare i seguenti personaggi:
Q w e r t y u i o pDividi questo insieme di caratteri alfabetici in due metà, dà:
Q w e r t y u i o pUn sub array si chiama corsa. Quindi il sotto -array sinistro, "Q w e r t" è una corsa e il sotto -array destro, "y u i o p" è anche una corsa. Una corsa può anche avere un solo elemento.
Fondanza/smistamento (conquista) entrambe le metà in un set dà:
E i o p q r t u w yIl codice da dividere per 2 è:
int imiddle = (ibegin + iend) / 2;Questa è una divisione intera. Quindi, viene presa la parte dell'intero numero del risultato. Con questo, se il numero totale di elementi nel set è dispari, la metà sinistra sarebbe più grande della metà destra, di 1 unità per indicizzazione basata su zero.
Per la dichiarazione sopra e il set, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', ibegin = 0, iend = 10 (che è l'ultimo indice di 9, più 1), imiddle = 5;
Il codice da unire/ordinamento (conquista) è:
int i = ibegin;int j = imiddle;
per (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
altro
Q [k] = p [j];
j = j + 1;
P è l'array dato. Q avrebbe l'array ordinato, in questo caso.
Se questo codice viene applicato sul set, "Q", "w", "e", "r", "t", "y", "u", 'i', 'o', 'p' , ci sarà la fusione delle metà divise, ma nessun smistamento (perché ogni elemento nella corsa a sinistra è inferiore a 'y'). Questo codice è rivisitato di seguito per mostrare la sua efficacia nell'ordinamento di una coppia consecutiva di corse.
Algoritmo pratico di divisione e conquista
L'intero programma Mergesort può essere scritto dall'alto verso il basso o dal basso verso l'alto. In questo articolo, il programma è scritto, top-down.
Un Mergesort opera concettualmente nel modo seguente:
1) Dividere il set non desiderato in N sottoinsiemi (corse), dove ciascuno ha un elemento. Si noti che viene considerato un solo set con un solo elemento.
2) Unisci ripetutamente sottoinsiemi per ottenere nuovi sottoinsiemi ordinati, fino a quando non viene lasciato un solo sottoinsieme. Questo è il set ordinato.
Con questi due punti, un determinato set non desiderato è diviso in due corse. Ognuna di queste due corse è registrata in memoria per la fusione/smistamento insieme, ma non si è ancora unito o ordinato. Ogni corsa di nuovo su entrambi i lati, è divisa in due. Le coppie consecutive di corse sono registrate per la fusione/smistamento insieme, ma non unite o risolte ancora. Questa divisione in due e la registrazione per la fusione/smistamento di coppie consecutive vengono ripetute fino a quando non vi è un solo elemento per corsa.
La registrazione in memoria per la fusione/smistamento di corse consecutive viene eseguita chiamando il codice di ordinamento sopra in modo ricorsivo dopo la divisione. Il codice di ordinamento è in una funzione separata. L'istruzione di divisione e la chiamata della funzione di ordinamento (che fa anche unione) sono in un segmento di codice (una funzione) con la dichiarazione di divisione digitata per prima.
Quando la divisione ha raggiunto lo stato delle corse a elemento singolo, le funzioni di fusione/smistamento registrate in memoria vengono chiamate in ordine inverso in cui sono state registrate. È una funzione di unione/ordinamento che è stata registrata in memoria molte volte con argomenti diversi. Le coppie consecutive di singoli elementi vengono ordinate per la prima volta, unendo allo stesso tempo. L'ordinamento e la fusione di corse consecutive continuano fino a quando l'intero set non viene risolto. Quindi, l'ordinamento non è proprio sulla disposizione degli elementi come è stato dato originariamente.
In C, è necessario un secondo array, la cui lunghezza è lunga quanto l'array dato. Inizialmente, devono essere effettuati tutti gli elementi per questo secondo array, il valore predefinito del tipo di dati. Gli elementi dell'array dato sono ordinati in questo secondo array. Quindi copiato di nuovo nell'array dato, sopravvalutando gli elementi non portati.
Per i caratteri, questo secondo array può essere creato e inizializzato come segue:
char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';int sz = sizeof (p)/sizeof (p [0]);
Char Q [SZ];
per (int i = 0; i
Qui, l'array dato è p e il secondo array è Q. Questo codice può essere nella funzione principale. In C/C ++ il carattere predefinito è "e non uno spazio ("). Tuttavia, poiché il compilatore G ++ non consentirebbe l'assegnazione di "a q [i], il singolo spazio ("), è stato assegnato.
Si noti che i valori predefiniti per gli elementi dell'array Q non sono realmente necessari per il programma Mergesort completo in quanto saranno comunque sovrascritti dagli elementi di interesse. Dichiarando l'array q con le sue dimensioni, sz è sufficiente.
Il set, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', è usato per spiegare come Mergesort si ottiene praticamente, in questa sezione. Dare Array Q Valori predefiniti è stato insegnato in questo articolo come conoscenza extra.
Il set è diviso nei due set:
'Q', 'w', 'e', 'r', 't' e 'y', 'u', 'i', 'o', 'p'Il codice di fusione/smistamento sopra viene chiamato come funzione ma l'ordinamento e la fusione non si verificano. Nel programma reale, l'ordinamento e la fusione di queste due corse sono registrati in memoria, prima. L'ordinamento e la fusione non saranno in definitiva necessariamente fatti su questi due particolari arrangiamenti di personaggi.
I due sottoinsiemi sopra sono ciascuno, ulteriormente divisi in due per avere:
'Q', 'W', 'e' e 'r', 't' e 'y', 'u', 'i' e 'o', 'p'Si noti che per ogni nuova divisione qui, il sottoinsieme sinistro è più lungo del sottoinsieme destro di un'unità.
Il codice di fusione/smistamento sopra è chiamato come funzione, per coppie consecutive di questi nuovi sottoinsiemi. Ma l'ordinamento e la fusione non si svolgono immediatamente. L'ordinamento e la fusione di queste coppie consecutive di corse sono registrate nella memoria del computer. L'ordinamento e la fusione non saranno in definitiva, necessariamente, sulla particolare disposizione dei personaggi di queste coppie consecutive di corse.
I sottoinsiemi di cui sopra sono ciascuno, ulteriormente divisi in due per avere:
'' Q ',' w ' e ' e ' e ' r ' e ' t ' e ' y ',' u ' e ' i ' e ' o ' e 'P'Viene registrato l'ordinamento e la fusione di coppie consecutive.
Qui, alcuni sottoinsiemi non possono essere più divisi perché ciascuno è costituito da un elemento. Quindi, la divisione dei sottoinsiemi più di una lunghezza sopra, porta a:
'Q' e 'w' e 'e' e 'r' e 't' e 'y' e 'u' e 'i' e ' O ' e ' p 'Viene registrato l'ordinamento e la fusione di coppie consecutive.
La funzione di smistamento e fusione è codificata in modo ricorsivo. E così, verrà chiamato nell'ordine invertito, per le molte volte, è stato registrato.
Quindi, 'q' e 'w' verranno ordinati e uniti in 'q', 'w'. 'E' e 'r' saranno ordinati e uniti in 'e', 'r'. 'T'. 'Y' verrà ordinato e unito in 't', 'y'. 'U' e 'i' saranno ordinati e uniti in 'i', 'u'. 'O'. 'P' verrà ordinato e unito in 'o', 'p'. La funzione di unione e di ordinamento sopra viene utilizzata qui; ed è usato per tutto.
Avanti: 'q', 'w' e 'e', 'r' verranno ordinati e uniti in 'e', 'q', 'r', 'w'. '' T ',' y ' e ' i ',' u ' verranno ordinati e uniti in, ' i ',' t ',' u ',' y '. In questa fase, 'o', 'p' non è unito a sottoinsiemi precedenti di due. La funzione di unione e di ordinamento sopra è stata utilizzata qui e viene utilizzata dappertutto.
La fase successiva: 'e', 'q', 'r', 'w' e 'i', 't', 'u', 'y' sono ordinati e unito in 'e', ' I ',' q ',' r ',' t ',' u ',' w ',' y '. In questa fase, 'o', 'p' di nuovo non è unito a nessuno dei sottoinsiemi precedenti.
L'ultima fase: 'e', 'i', 'q', 'r', 't', 'u', 'w', 'y' e 'o', p ' sono ordinati e uniti in 'e', 'i', 'o', 'p', 'q', 'r', 't', 'u', 'w', 'y'. Il set non desiderato è stato ordinato.
Codificando Mersort in C
L'attività è ordinare l'array P e non l'array q. Quindi, per l'intero programma Mergesort, Array Q viene prima creato una copia di Array P. Il programma quindi ordina l'array q in array p. Questo non è proprio ciò che è insinuato sopra. Esistono quattro funzioni per il programma Mergesort completo.
La funzione per dividere e unire
Questa è la funzione principale nel programma. Ricordiamo che la fusione prevede anche l'ordinamento delle corse consecutive sinistro e destro. Questa fusione è in memoria e in realtà inizia quando l'array è stato diviso per due e due e due ecc. Fino a quando non c'è solo un elemento per corsa. Quindi, l'ordinamento e la fusione iniziano in quella fase con una coppia per un elemento per corsa. Lo scheletro della funzione di smistamento è:
void topdownsplitmerge (char q [], int ibegin, int iend, char p [])| |
// Dividi il sottoinsieme più lungo di 1 elemento in due
int imiddle = (ibegin + iend) / 2; // imiddle è il punto medio
| |
| |
| |
// unisci i sottoinsiemi risultanti dall'array q [] in p []
topdownmerge (Q, ibegin, imiddle, iend, p);
Questa funzione prende l'array dato come Q che in questo caso è in realtà l'array di copia q. Prende anche l'array di copia come p che in questo caso è in realtà l'array dato p. Per la prima chiamata di questa funzione, ibegin = 0 e iend = n, dove n ha la dimensione di entrambi gli array. Questi sono a causa dell'impiego a zero indicizzato dell'array.
Dopo una divisione di due, Ibegin sarà il primo indice della corsa sinistra e Iend sarà l'ultimo indice della corsa consecutiva a destra. La divisione per due dà l'intero, imiddle, ignorando il resto. Questo è l'ultimo indice della corsa sinistra e anche il primo indice della corsa destra. Questa ambiguità viene eliminata dalla condizione while del codice di smistamento.
L'ultima istruzione nel codice sopra è una chiamata alla funzione di unione e ordinamento precisa. Questa chiamata va alla memoria, quando viene chiamata. Sarà eseguito in ordine invertito per tutte le sue chiamate perché è una chiamata ricorsiva. Prende le variabili come argomenti. Q, Ibegin, Iend e P, ricevuti dalla funzione codificata esterna. Imiddle, che è anche uno dei suoi argomenti, viene creato all'interno della funzione codificata esterna, sopra la chiamata.
È all'interno di questa funzione codificata esterna che le corse sinistra e destra devono essere identificate (divise). Questo è meglio effettuando una chiamata ricorsiva alla funzione codificata esterna come segue (alcuni codice incluso nella definizione della funzione):
void topdownsplitmerge (char q [], int ibegin, int iend, char p [])// Dividi il sottoinsieme più lungo di 1 elemento in due
int imiddle = (ibegin + iend) / 2; // imiddle è il punto medio
// ordina in modo ricorsivo entrambe le corse dall'array A [] in B []
topdownsplitmerge (p, ibegin, imiddle, q); // Dividi il sottoinsieme sinistro in due per l'ordinamento, dopo la memorizzazione
topdownsplitmerge (p, imiddle, iend, q); // Dividi il sottoinsieme giusto in due per l'ordinamento, dopo la memorizzazione
// unisci i sottoinsiemi risultanti dall'array q [] in p []
topdownmerge (Q, ibegin, imiddle, iend, p);
Le due nuove chiamate ricorsive sono state digitate sopra la chiamata ricorsiva topdownmerge (). Queste due chiamate saranno memorizzate insieme a Topdownmerge () e chiamate tutte le volte necessarie, ciascuna in ordine inverso.
Se l'array dato non ha elementi, non dovrebbe esserci smistamento. Se il numero di elementi nell'array dato è 1, allora l'array è già ordinato e non dovrebbe aver luogo alcun ordinamento. Questo è curato da una dichiarazione all'interno ma nella parte superiore della funzione codificata esterna, TopdownSplitMerge () come segue:
void topdownsplitmerge (char q [], int ibegin, int iend, char p [])if (iend - ibegin<= 1)
ritorno;
int imiddle = (ibegin + iend) / 2;
topdownsplitmerge (p, ibegin, imiddle, q);
topdownsplitmerge (p, imiddle, iend, q);
topdownmerge (Q, ibegin, imiddle, iend, p);
La funzione precisa per unirsi e ordinare
Il nome di questa funzione è topdownmerge (). Si chiama ricorsivamente da topdownsplitmerge (). Il codice è:
void topdownmerge (char p [], int ibegin, int imiddle, int iend, char q [])// Mentre ci sono elementi nei sottoinsiemi sinistro o destro ..
int i = ibegin;
int j = imiddle;
per (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
altro
Q [k] = p [j];
j = j + 1;
In teoria, questa funzione itera dall'inizio della corsa sinistra (sottoinsieme) fino alla fine della corsa destra (sottoinsieme). Nota come l'ambiguità sopra menzionata è stata curata dalla condizione temporale della costruzione IF.
Fare una copia una tantum per tutti gli elementi
All'inizio del programma, dopo la funzione di seguito (questa sezione), è stato chiamato, tutti gli elementi dell'array dato devono essere copiati nell'array, Q. Il codice per questo è:
void CopyArray (char p [], int ibegin, int iend, char q [])per (int i = ibegin; i
Si chiama una volta dalla seguente funzione. Questo prende come argomenti, l'array dato, p, quindi 0, quindi N e l'altro array q, che in teoria è vuoto ma ha già lo stesso numero di elementi di p. Iend, che è uguale a n, qui, è la lunghezza dell'array originariamente dato.
Funzione per dare il via al programma
La funzione per iniziare il programma è:
void topdownmergesort (char p [], char q [], int n)CopyArray (P, 0, N, Q); // p [] viene copiato su Q [] una volta
topdownsplitmerge (q, 0, n, p);
Chiama la funzione CopyArray (), con gli argomenti previsti. Chiama successivamente la funzione principale, TopdownSplitMerge (), con le posizioni degli array, P e Q,. Questo è il motivo per cui, nel codice topdownmerge (), i valori ordinati vengono inviati a q e non a p.
Disposizione del codice
Se le quattro funzioni codificate sopra, vengono digitate nel seguente ordine,
- void topdownmerge ()
- void topdownsplitmerge ()
- CopyArray ()
- topDownMerGesort ()
quindi il programma Mergesort (costituito principalmente da queste quattro funzioni) funzionerà in un compilatore C senza alcun problema.
C Funzione principale
Una funzione principale C di questo programma è:
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];
per (int i = 0; i
TopDownMerGesort (P, Q, SZ);
per (int i = 0; i
printf ("\ n");
restituzione 0;
Conclusione
Dividere e conquistare l'algoritmo divide il problema in pezzi più piccoli, con la speranza di risolverli in modo indipendente. Dopo che tutti i pezzi più piccoli sono stati risolti, le loro soluzioni sono combinate in una soluzione principale. Con Mconde-Sort, c'è una divisione continua di due, fino a quando ogni sottoinsieme è lungo un elemento e automaticamente già ordinato. Mettere insieme questi singoli elementi, prevede funzioni ricorsive e ordinamento effettivo, a cominciare da coppie di singoli elementi.