Kuidas rakendada ühendamise sortimist näidetes C ++

Mis on ühendamise sort? Ühenda sortimine on võrdluspõhine sortimisalgoritm, mis kuulub jagamise ja vallutamise kategooriasse. Ühenda sortimist kasutatakse massiivi sortimiseks jagamise ja vallutamise strateegia põhjal, mida käsitletakse lühidalt selles postituses koos teiste mõistetega, näiteks selle algoritm koos näitega. Vaatame ka ühendamissordi keerukust ajalises keerukuses C ++ keeles

Järgmisi näpunäiteid käsitletakse selles artiklis,

• Jagage ja vallutage algoritm
• Ühendamise sortimisalgoritmi mõistmine näitega
• Ühendamise sortimise pseudokood
• Programm ühendamise sortimiseks C ++ keeles
• Ühendamise sortimise ajaline keerukus

Selle artikliga edasi liikumine Sorteeri ühendamine C ++ -s

Jaga ja võida algoritm

Kui olete quicksorti toimimisega juba tuttav, võite olla teadlik jagamise ja vallutamise strateegiast. Jaga ja võida hõlmab kolme suurt sammu. Nende sammude mõistmiseks kaalume massiivi Tere [], millel on algusindeks „a” ja lõppindeks „n”, seega võime massiivi kirjutada järgmiselt: Tere [a & hellip..n]

Jaga - esmane käik ehk jagamise ja vallutamise peamine samm on antud probleemi jagamine alamprobleemideks või alamosadeks. Konks on selles, et alamprobleemid peaksid olema algse probleemiga sarnased ja väiksema suurusega. Meie juhul jagame oma massiivi kaheks pooleks [a & hellip.m] [m + 1 & hellip..n] m asub a ja n indeksi keskel

Valluta - kui oleme lõpetanud oma probleemi jagamise alamprobleemideks. Lahendame need alamprobleemid rekursiivselt.

Kombineeri - selles etapis ühendame kõik oma alamprobleemide lahendused sobival viisil. Teisisõnu, ühendame 2 erinevat sorteeritud massiivi ühe sorteeritud massiivi moodustamiseks. Seal on meil sorteeritud massiiv.

Selle artikliga edasi liikumine Sorteeri ühendamine C ++ -s

Ühendamise sortimise algoritmi mõistmine näitega

Siinkohal teame, millist lähenemisviisi ühendamise sort kasutab. Vaatame näiteid ja läbime kõik sammud Hello [] sortimata massiivi.
Näide - Tere [10, 3, 7, 1, 15, 14, 9, 22]

Ülaltoodud pildil käsitlesime sorteerimata massiivi ja kasutasime sorteeritud massiivi saamiseks liitmise sortimist. Vaatame nüüd iga sammu ja mõistame kogu algoritmi

1. Kõigepealt pidasime massiivi Tere [10, 3, 7, 1, 15, 14, 9, 22]. Selles massiivis on kokku 8 elementi

2. Nagu nägime varem, kasutab sort sort elementide sortimiseks jagamise ja vallutamise lähenemist. Leidsime m, mis asub meie massiivi keskel, ja jagasime oma massiivi keskelt, kus m = (a - n) / 2 'a' on vasakpoolseima elemendi indeks ja n on meie massiivi parempoolseima elemendi indeks .

3. Pärast esimest jaotust on meil 2 osa, mis koosnevad 4 elemendist. Vaatame esimest poolaega [10, 3, 7, 1].

fibonacci number c ++

4. Jagame [10, 3, 7, 1] kaheks osaks [10, 3] ja [7, 1]. Pärast seda jagame need edasi [10], [3], [7], [1]. Edasine jagamine pole võimalik, kuna me ei saa arvutada m. ühte elementi sisaldav loend loetakse alati sorteerituks.

5. Kuidas toimub ühinemine? Uurime välja. Esiteks [10] ja [3] võrreldakse ja liidetakse kasvavas järjekorras [3, 10] samamoodi nagu saame [1, 7]

6. Pärast seda võrdleme [3, 10] ja [1, 7]. Kui võrrelda, ühendame need kasvavas järjekorras ja saame [1, 3, 7, 10].

7. [15, 14, 9, 2] on samuti jagatud ja ühendatud sarnasel viisil, moodustades vormid [9, 14, 15, 22].

8. Viimases etapis võrdleme ja kombineerime [15, 14, 9, 2] [9, 14, 15, 22], et saada meie sorteeritud massiivst [1, 3, 7, 9, 10, 14, 15, 22].

Selle artikliga edasi liikumine Sorteeri ühendamine C ++ -s

Ühendamise sortimise pseudokood

Alustage, kui see jääb
Funktsioon mergeSort () kutsub ennast rekursiivselt meie massiivi jagama, kuni sellest saab üks element ja funktsiooni sulandamist () kasutatakse sorteeritud massiivide ühendamiseks.
  Selle artikliga edasi liikumine Sorteeri ühendamine C ++ -s
 Ühenda sortimisprogramm C ++ keeles 
#include #include #include nimeruumi kasutamine standard void merge (int a [], int Firstindex, int m, int Lastindex) // liidab alammassiivid, mis on loodud jagamise void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsuurus int Tere [suurus], i cout<<'Enter the elements of the array one by one:n' for(i=0 i>Tere, [i] mergeSort (Tere, 0, suurus - 1) cout<<'The Sorted List isn' for(i=0 i
 Väljund- 
Selle artikliga edasi liikumine Sorteeri ühendamine C ++ -s
 Aja keerukus 
Aja keerukus on oluline aspekt, mida tuleb arvestada, kui räägime algoritmidest. Sorteerimise ühendamisel on võrreldes teiste sortimisalgoritmidega suur ajaline keerukus.
Halvimal juhul töötamise aeg - O (n log n) 
Parima juhtumi aeg - O (n log n) 
Keskmine jooksuaeg - O (n log n)
Sellega jõuame selle ühendamise sordi C ++ artiklis lõppu. Kui soovite rohkem teada saada, vaadake järgmist   autor Edureka, usaldusväärne veebipõhine õppefirma. Edureka Java J2EE ja SOA koolitus- ja sertifitseerimiskursus on mõeldud selleks, et õpetada teid nii Java-põhimõistete kui ka edasijõudnute kontseptsioonide jaoks koos erinevate Java-raamistikega nagu Hibernate & Spring.
 Kas teil on meile küsimus? Palun mainige seda selle ajaveebi kommentaaride jaotises ja võtame teiega ühendust niipea kui võimalik.