Ako implementovať zlúčenie zoradenia v C ++ s príkladmi

Čo je to druh zlúčenia? Zlúčiť zoradenie je porovnávací algoritmus založený na porovnávaní, ktorý patrí do kategórie rozdelenia a dobytia. Merge sort sa používa na triedenie poľa na základe stratégie rozdelenia a dobytia, ktorá bude v tomto príspevku stručne popísaná spolu s ďalšími konceptmi, ako je napríklad jeho algoritmus s príkladom. Pozrime sa tiež na časovú zložitosť spôsobu zlučovania v C ++

V tomto článku sa budeme zaoberať nasledujúcimi ukazovateľmi,

• Algoritmus rozdeľuj a panuj
• Pochopenie algoritmu zlučovania zoradenia s príkladom
• Pseudokód pre zlúčenie zoradenia
• Program v C ++ na zlúčenie
• Časová zložitosť zlúčenia

Pokračujeme týmto článkom o zlúčení zoradenia v C ++

Algoritmus Divide and Conquer

Ak už viete, ako funguje quicksort, môžete si byť vedomí stratégie rozdelenia a panovania. Rozdeľ a panuj zahŕňa tri hlavné kroky. Pre pochopenie týchto krokov zvážime pole Hello [] so začiatočným indexom ‘a’ a končiacim indexom ‘n’, preto môžeme naše pole zapísať nasledujúcim spôsobom Hello [a & hellip..n]

Rozdeliť - Prvotným ťahom alebo hlavným krokom rozdelenia a dobytia je rozdelenie daného problému na čiastkové problémy alebo čiastkové časti. Háčik je v tom, že čiastkové problémy by mali byť podobné pôvodným problémom a mali by byť menšie. V našom prípade rozdelíme naše pole na 2 polovice [a & hellip.m] [m + 1 & hellip..n] m leží v strede indexu a n

Dobyť - Akonáhle skončíme, rozdelíme náš problém na čiastkové problémy. Tieto podproblémy riešime rekurzívne.

Kombinovať - ​​V tomto kroku vhodným spôsobom kombinujeme všetky riešenia našich čiastkových problémov. Inými slovami, skombinujeme 2 rôzne zoradené polia do jedného zoradeného poľa. Tam máme zoradené pole.

Pokračujeme týmto článkom o zlúčení zoradenia v C ++

Pochopenie algoritmu zlúčenia zoradenia s príkladom

V tomto okamihu vieme, aký prístup použije druh zlúčenia. Zoberme si teda príklad a prejdime každý krok od Hello [] netriedeného po zoradené pole.
Príklad - Dobrý deň [10, 3, 7, 1, 15, 14, 9, 22]

ako to urobiť s mocou v

Na obrázku vyššie sme uvažovali o netriedenom poli a na získanie zoradeného poľa sme použili zlúčenie. Pozrime sa teraz na každý krok a pochopme celý algoritmus

1. Najprv sme považovali pole Hello [10, 3, 7, 1, 15, 14, 9, 22] v tomto poli je celkovo 8 prvkov

2. Ako sme videli skôr, pri zlúčení sa pri triedení prvkov používa prístup rozdelenia a dobývania. Našli sme m, ktoré leží v strede nášho poľa a rozdelili sme naše pole od stredu, kde m = (a - n) / 2 'a' je index prvku úplne vľavo a n je index prvku úplne vpravo z nášho poľa .

3. Po prvom rozdelení máme 2 časti pozostávajúce po 4 prvkoch. Pozrime sa na prvú polovicu [10, 3, 7, 1].

4. Rozdelíme [10, 3, 7, 1] na 2 časti [10, 3] a [7, 1]. Potom ich rozdelíme ďalej na [10], [3], [7], [1]. Ďalšie delenie nie je možné, pretože nemôžeme vypočítať m. zoznam obsahujúci jeden prvok sa vždy považuje za triedený.

5. Ako prebieha zlúčenie? Poďme zistiť. Najskôr sa porovnajú [10] a [3] a zlúčia sa vzostupne [3, 10] rovnakým spôsobom, ako dostaneme [1, 7]

získaj dĺžku poľa js

6. Potom porovnávame [3, 10] a [1, 7]. Po porovnaní ich zlúčime vzostupne a dostaneme [1, 3, 7, 10].

7. [15, 14, 9, 2] je tiež rozdelený a kombinovaný podobným spôsobom do formy [9, 14, 15, 22].

8. V poslednom kroku porovnáme a skombinujeme [15, 14, 9, 2] [9, 14, 15, 22], aby sme získali zoradené poletj [1, 3, 7, 9, 10, 14, 15, 22].

casting double na int java

Pokračujeme týmto článkom o zlúčení zoradenia v C ++

Pseudokód pre zlúčenie zoradenia

Začnite, ak zostane
Funkcia mergeSort () sa rekurzívne volá, aby rozdelila naše pole, až kým sa nestane jedným prvkom, a na zlúčenie zoradených polí sa použije funkcia merge ().
  Pokračujeme týmto článkom o zlúčení zoradenia v C ++
 Zlúčiť program triedenia v C ++ 
#include #include #include using namespace std void merge (int a [], int Firstindex, int m, int Lastindex) // zlúči čiastkové polia, ktoré sú vytvorené pri rozdelení void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Ahoj [size], ja cout<<'Enter the elements of the array one by one:n' for(i=0 i>Dobrý deň [i] mergeSort (Hello, 0, veľkosť - 1) cout<<'The Sorted List isn' for(i=0 i
 Výkon- 
Pokračujeme týmto článkom o zlúčení zoradenia v C ++
 Časová zložitosť 
Časová zložitosť je dôležitý aspekt, ktorý treba brať do úvahy, keď hovoríme o algoritmoch. Zlúčenie zoradenia sa považuje za veľmi zložité v porovnaní s inými algoritmami triedenia.
Najhorší čas chodu - O (n log n) 
Najlepší čas chodu - O (n log n) 
Priemerná doba chodu - O (n log n)
Týmto sa dostávame na koniec tohto článku Zlúčenie v C ++. Ak sa chcete dozvedieť viac, pozrite si   Edureka, dôveryhodná online vzdelávacia spoločnosť. Výcvikový a certifikačný kurz Edureka Java J2EE a SOA je navrhnutý tak, aby vás vyškolil pre základné aj pokročilé koncepty Java spolu s rôznymi rámcami Java, ako je Hibernate & Spring.
 Máte na nás otázku? Uveďte to prosím v sekcii komentárov tohto blogu a my sa vám ozveme čo najskôr.