Slå sammen i C
Fusjonsprogrammet, skrevet normalt, er sammenlignbart (når det gjelder hastighet) med sort () -funksjonen levert av C ++ i algoritmiblioteket. Merge-sort er også et kommersielt program for generell formål.
Denne artikkelen forklarer hvordan du skriver MergeSort -programmet på C -språket.
Dele-og-erobre algoritme, i sin bred forstand
I sin bred forstand er utvalget av elementer delt inn i to halvdeler: venstre halvdel og høyre halvdel. Hvis det totale antallet elementer som skal sorteres er rart, blir venstre halvdel gjort større enn høyre halvdel, med 1 enhet. Ellers har begge halvdelene av samme lengde. De to halvdelene blir deretter slått sammen mens de sorterer for å danne en sortert matrise. Sammenslåing/sortering erobrer. Tenk på følgende tegn som skal sorteres:
Q w e r t y u i o pÅ dele dette settet med alfabetiske tegn i to halvdeler, gir:
Q w e r t y u i o pEn undergruppe kalles et løp. Så venstre underoppstilling, “Q w e r t” er et løp og høyre underoppstilling, “y u i o p” er også et løp. Et løp kan også bare ha ett element.
Sammenslåing/sortering (erobring) begge halvdeler til ett sett gir:
E i o p q r t u w yKoden som skal deles med 2 er:
int imiddle = (ibegin + iend) / 2;Dette er heltalldivisjon. Så hele antallet del av resultatet blir tatt. Med dette, hvis det totale antall elementer i settet er rart, ville venstre halvdel være større enn høyre halvdel, med 1 enhet for nullbasert indeksering.
For ovennevnte uttalelse og settet, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', ibegin = 0, iend = 10 (som er siste indeks på 9, pluss 1), imiddle = 5;
Koden for å slå sammen/sortere (erobre) er:
int i = ibegin;int j = imiddle;
for (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
annet
Q [k] = p [j];
j = j + 1;
P er den gitte matrisen. Q ville ha den sorterte matrisen, i dette tilfellet.
Hvis denne koden brukes på settet, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p' , vil det være sammenslåing av de delte halvdelene, men ingen sortering (fordi hvert element i venstre kjøring er mindre enn 'y'). Denne koden blir revidert nedenfor for å vise sin effektivitet i å sortere et påfølgende par løp.
Praktisk splittelses- og erobringsalgoritme
Hele sammenslåingsprogrammet kan skrives ovenfra og ned eller bottom opp. I denne artikkelen er programmet skrevet, ovenfra og ned.
En sammenslåing fungerer konseptuelt på følgende måte:
1) Del det usorterte settet i n undergrupper (kjører), der hver har ett element. Merk at et sett med bare ett element anses som sortert.
2) Fusjoner gjentatte ganger undergrupper for å få nye sorterte undergrupper, inntil bare ett undergruppe er igjen. Dette er det sorterte settet.
Med disse to punktene er et gitt usortert sett delt inn i to løp. Hver av disse to løpene er spilt inn i minnet for sammenslåing/sortering sammen, men ikke slått sammen eller sortert ennå. Hvert løp igjen på hver side, er delt inn i to. De påfølgende par løpene er spilt inn for sammenslåing/sortering sammen, men ikke slått sammen eller sortert fremdeles ennå. Denne inndelingen i to og opptak for sammenslåing/sortering av par på rad gjentas til det bare er ett element per kjøring.
Innspillingen i minnet for sammenslåing/sortering sammen av påfølgende løp gjøres ved å ringe ovennevnte sorteringskode rekursivt etter divisjon. Sorteringskoden er i en separert funksjon. Divisjonserklæringen og kallet til sorteringsfunksjonen (som også gjør sammenslåing) er i ett kodesegment (en funksjon) med divisjonserklæringen skrevet først.
Når divisjonen har nådd tilstanden til enkeltelementkjøringer, kalles sammenslåings-/sorteringsfunksjonene som er registrert i minnet i omvendt rekkefølge der de ble registrert. Det er en fusjons-/sorteringsfunksjon som ble registrert i minnet mange ganger med forskjellige argumenter. Påfølgende par av enkeltelementer blir først sortert, samtidig som samtidig. Sortering og sammenslåing av påfølgende løp fortsetter til hele settet er sortert. Så sorteringen er egentlig ikke på arrangementet av elementer som ble gitt opprinnelig.
I C er det behov for et nytt utvalg, hvis lengde er så lang som den gitte matrisen. Til å begynne med må alle elementene for denne andre matrisen lages, standardverdien for datatypen. Elementene i den gitte matrisen er sortert i denne andre matrisen. Deretter kopiert tilbake til den gitte matrisen, og overstyrte de usorterte elementene.
For tegn kan denne andre matrisen opprettes og initialiseres som følger:
char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';int sz = størrelse av (p)/størrelse av (p [0]);
char q [sz];
for (int i = 0; i
Her er den gitte matrisen P, og den andre matrisen er Q. Denne koden kan være i hovedfunksjonen. I C/C ++ er standardkarakteren "og ikke et rom ("). Siden G ++ -kompilatoren ikke ville tillate tildeling av "til Q [i], ble det eneste rommet (") tildelt.
Merk at standardverdiene for Array Q -elementer egentlig ikke er nødvendige for det komplette sammenslåingsprogrammet, da de fremdeles vil bli overstyrt av elementene av interesse. Erklærende matrise q med sin størrelse, SZ er tilstrekkelig.
Settet, 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', brukes til å forklare hvordan Fusjonsort oppnås praktisk talt, i denne delen. Å gi matrise Q -standardverdier har blitt undervist i denne artikkelen som ekstra kunnskap.
Settet er delt inn i de to settene:
'Q', 'w', 'e', 'r', 't' og 'y', 'u', 'i', 'o', 'p'Ovennevnte sammenslåing/sorteringskode kalles en funksjon, men sortering og sammenslåing finner ikke sted. I det virkelige programmet blir sortering og sammenslåing av disse to løpene spilt inn i minnet, først. Sortering og sammenslåing vil ikke til slutt nødvendigvis bli gjort på disse to spesielle ordningene av karakterer.
Ovennevnte to undergrupper er hver, videre delt inn i to for å ha:
'Q', 'w', 'e' og 'r', 't' og 'y', 'u', 'i' og 'o', 'p'Merk at for hver nye divisjon her er venstre delmengde lengre enn høyre delmengde av en enhet.
Ovennevnte sammenslåing/sorteringskode kalles en funksjon, for påfølgende par av disse nye undergruppene. Men sortering og sammenslåing foregår ikke umiddelbart. Sortering og sammenslåing av disse påfølgende par løpene er spilt inn i datamaskinens minne. Sortering og sammenslåing vil ikke til syvende og sist, nødvendigvis gjøres, på den spesielle arrangementet av karakterer av disse påfølgende par løpene.
Ovennevnte undergrupper er hver, videre delt inn i to for å ha:
'Q', 'w' og 'e' og 'r' og 't' og 'y', 'u' og 'i' og 'o' og 'P'Sortering og sammenslåing av påfølgende par blir spilt inn.
Her kan noen undergrupper ikke deles mer fordi de hver består av ett element. Deretter fører deling av mer enn en lengde undergrupper ovenfor:
'Q' og 'w' og 'e' og 'r' og 't' og 'y' og 'u' og 'i' og '' O ' og ' p 'Sortering og sammenslåing av påfølgende par blir spilt inn.
Sorterings- og sammenslåingsfunksjonen er kodet på en rekursiv måte. Og slik vil det bli kalt i den omvendte orden, for mange ganger ble den spilt inn.
Så, 'q' og 'w' vil bli sortert og slått sammen til 'q', 'w'. 'E' og 'r' vil bli sortert og slått sammen til 'e', 'r'. 'T'. 'Y' vil bli sortert og slått sammen til 't', 'y'. 'U' og 'i' vil bli sortert og slått sammen til 'i', 'u'. 'O'. 'P' vil bli sortert og slått sammen til 'o', 'p'. Ovennevnte fusjons- og sorteringsfunksjon brukes her; Og det brukes gjennom hele.
Neste: 'q', 'w' og 'e', 'r' vil bli sortert og slått sammen til 'e', 'q', 'r', 'w'. 'T', 'y' og 'i', 'u' vil bli sortert og slått sammen til, 'i', 't', 'u', 'y'. På dette stadiet er 'o', 'p' ikke sammen med noen tidligere undergrupper av to. Ovennevnte fusjons- og sorteringsfunksjon har blitt brukt her og brukes gjennom hele.
Neste trinn: 'e', 'q', 'r', 'w' og 'i', 't', 'u', 'y' er sortert og slått sammen til 'e', ' I ',' q ',' r ',' t ',' u ',' w ',' y '. På dette stadiet er 'o', 'p' igjen ikke sammen med noen av de tidligere undergruppene.
Det siste trinnet: 'e', 'i', 'q', 'r', 't', 'u', 'w', 'y' og 'o', p ' er sortert og sammenslått inn i 'e', 'i', 'o', 'p', 'q', 'r', 't', 'u', 'w', 'y'. Det usorterte settet er sortert.
Koding Mersort i C
Oppgaven er å sortere matrise P og ikke matrise q. Så for hele sammenslåingsprogrammet er Array Q først laget en kopi av Array P. Programmet sorterer deretter matrise Q til matrise P. Dette er ikke helt det som er antydet ovenfor. Det er fire funksjoner for det komplette MergeSort -programmet.
Funksjonen for å dele og slå sammen
Dette er hovedfunksjonen i programmet. Husk at sammenslåing også innebærer sortering av venstre og høyre påfølgende løp. Denne sammenslåingen er i minnet og begynner faktisk når matrisen har blitt delt med to og to og to osv. til det bare er ett element per løp. Så sortering og sammenslåing begynner på det stadiet med et par for ett element per løp. Skjelettet for sorteringsfunksjonen er:
void topdownSplitMerge (char q [], int ibegin, int iend, char p [])| |
// del delmengden lenger enn 1 element i to
int imiddle = (ibegin + iend) / 2; // Imiddle er midtpunktet
| |
| |
| |
// Slå sammen de resulterende undergruppene fra Array Q [] til P []
topdownmerge (q, ibegin, imiddle, iend, p);
Denne funksjonen tar den gitte matrisen som q som i dette tilfellet faktisk er kopieringsoppstillingen q. Det tar også kopieringen som P som i dette tilfellet faktisk er den gitte matrisen P. For den første samtalen med denne funksjonen, iBegin = 0 og Iend = n, hvor n er størrelsen på begge matriser. Disse er på grunn av nullindeksert sysselsetting av matrisen.
Etter en divisjon av to, vil Ibegin være den første indeksen for venstre løp, og Iend vil være den siste indeksen for påfølgende høyre løp. Deling av to gir heltallet, Imiddle, ignorerer resten. Dette er den siste indeksen for venstre kjøring og også den første indeksen for høyre løp. Denne tvetydigheten elimineres av mens-betingelsen av sorteringskoden.
Den siste uttalelsen i koden over er en samtale til den nøyaktige fusjons- og sorteringsfunksjonen. Denne samtalen går til minnet, når den blir kalt. Det vil bli utført i reversert ordre for alle samtaler fordi det er en rekursiv samtale. Det tar variablene som argumenter. Q, Ibegin, Iend og P, mottatt av den ytre kodede funksjonen. Imiddle, som også er et av argumentene, opprettes i den ytre kodede funksjonen, over samtalen.
Det er inne i denne ytre kodede funksjonen at venstre og høyre løp må identifiseres (delt). Dette gjøres best ved å ringe en rekursiv samtale til den ytre kodede funksjonen som følger (noen koder inkludert i funksjonsdefinisjon):
void topdownSplitMerge (char q [], int ibegin, int iend, char p [])// del delmengden lenger enn 1 element i to
int imiddle = (ibegin + iend) / 2; // Imiddle er midtpunktet
// Rekursivt sorterer begge kjøres fra matrise A [] til B []
TopdownSplitMerge (P, Ibegin, Imiddle, Q); // Del venstre delmengde i to for sortering, etter memorering
TopdownSplitMerge (P, Imiddle, Iend, Q); // Del høyre delmengde i to for sortering, etter memorering
// Slå sammen de resulterende undergruppene fra Array Q [] til P []
topdownmerge (q, ibegin, imiddle, iend, p);
De to nye rekursive samtalene har blitt skrevet over den topdownmerge () rekursive samtalen. Disse to samtalene vil bli husket sammen med topdownmerge () og kalt så mange ganger som nødvendig, hver i omvendt rekkefølge.
Hvis den gitte matrisen ikke har noe element, skal det ikke være noe sortering. Hvis antall elementer i den gitte matrisen er 1, er matrisen allerede sortert, og ingen sortering skal finne sted. Dette blir ivaretatt av en uttalelse inne, men øverst i den ytre kodede funksjonen, topdownSplitMerge () som følger:
void topdownSplitMerge (char q [], int ibegin, int iend, char p [])if (iend - ibegin<= 1)
komme tilbake;
int imiddle = (ibegin + iend) / 2;
TopdownSplitMerge (P, Ibegin, Imiddle, Q);
TopdownSplitMerge (P, Imiddle, Iend, Q);
topdownmerge (q, ibegin, imiddle, iend, p);
Den nøyaktige funksjonen for å slå sammen og sortere
Navnet på denne funksjonen er topdownmerge (). Det kalles rekursivt av TopdownSplitMerge (). Koden er:
void topdownmerge (char p [], int ibegin, int imiddle, int iend, char q [])// mens det er elementer i venstre eller høyre undergrupper ..
int i = ibegin;
int j = imiddle;
for (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
annet
Q [k] = p [j];
j = j + 1;
I teorien itererer denne funksjonen fra begynnelsen av venstre kjøring (undergruppe) til slutten av høyre kjøring (undergruppe). Legg merke til hvordan tvetydigheten som er nevnt ovenfor, har blitt ivaretatt av mens-betingelsen av IF-konstruksjonen.
Gjør engangskopi for alle elementene
I begynnelsen av programmet, etter funksjonen nedenfor (denne delen), er blitt kalt, må alle elementene i den gitte matrisen kopieres til matrisen, q. Koden for det er:
void copyArray (char p [], int ibegin, int iend, char q [])for (int i = ibegin; i
Det kalles en gang fra følgende funksjon. Dette tar som argumenter, den gitte matrisen, P, deretter 0, deretter n, og den andre matrisen Q, som er i teorien tomt, men allerede har samme antall elementer som P. Jeg er det samme som N, her, er lengden på den opprinnelig gitte matrisen.
Funksjon for å starte programmet
Funksjonen for å starte programmet er:
void topdownMergesort (char p [], char q [], int n)copyArray (p, 0, n, q); // p [] kopieres til Q [] en gang
topdownSplitMerge (q, 0, n, p);
Det kaller copyArray () -funksjonen, med de forventede argumentene. Det kaller neste hovedfunksjon, topdownSplitMerge (), med posisjonene til matriser, p og q, byttet ut. Dette er grunnen til at i TopDownMerge () koden blir sorterte verdier sendt til Q og ikke til P.
Kodearrangement
Hvis de fire kodede funksjonene ovenfor, skrives inn i følgende rekkefølge,
- void topdownmerge ()
- void topdownSplitMerge ()
- copyArray ()
- topdownMergesort ()
da vil MergeSort -programmet (hovedsakelig bestående av disse fire funksjonene) fungere i en C -kompilator uten problemer.
C Hovedfunksjon
En passende C hovedfunksjon for dette programmet er:
int main (int argc, char ** argv)char p [] = 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p';
int sz = størrelse av (p)/størrelse av (p [0]);
char q [sz];
for (int i = 0; i
TopDownMergesort (P, Q, SZ);
for (int i = 0; i
printf ("\ n");
retur 0;
Konklusjon
Del og erobre algoritme deler problemet i mindre biter, med håp om å løse dem uavhengig. Etter at alle de mindre brikkene er løst, er løsningene deres kombinert til en hovedløsning. Med sammenslåing er det kontinuerlig inndeling av to, inntil hvert delmengde er ett element langt, og automatisk allerede sortert. Å bringe disse enkeltelementets løp sammen, involverer rekursive funksjoner og faktisk sortering, som begynner med par enkeltelementer.