Menu

Zlúčiť zoradenie v C ++ s príkladmi

merge sort c with examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Technika zlúčenia a zlúčenia v C ++.

Algoritmus zlúčenia triedenia používa „ rozdeliť a dobyť ”Stratégia, v rámci ktorej rozdelíme problém na podproblémy a tieto podproblémy riešime jednotlivo.

Tieto čiastkové problémy sa potom skombinujú alebo spoja, aby vytvorili jednotné riešenie.

=> Prečítajte si populárnu sériu školení C ++ tu.

Zlúčiť zoradenie

Čo sa dozviete:

aplikácia pre prevod z youtube na mp4 pre Android

Prehľad

Zlúčenie sa uskutoční pomocou nasledujúcich krokov:

# 1) Zoznam, ktorý sa má triediť, je rozdelený na dve polia rovnakej dĺžky vydelením zoznamu na strednom prvku. Ak je počet prvkov v zozname buď 0, alebo 1, potom sa zoznam považuje za triedený.

#dva) Každý podzoznam je zoradený individuálne pomocou rekurzívneho zlučovania.

# 3) Zoradené podzoznamy sa potom skombinujú alebo zlúčia do jedného úplného zoradeného zoznamu.

Všeobecný algoritmus

Všeobecný pseudokód pre techniku ​​zlučovania je uvedený nižšie.

Vyhláste pole Arr o dĺžke N
Ak N = 1, Arr je už zoradený
Ak N> 1,
Vľavo = 0, vpravo = N-1
Nájdite stred = (vľavo + vpravo) / 2
Volať merge_sort (Arr, ľavý, stredný) => triediť prvú polovicu rekurzívne
Volať merge_sort (Arr, stred + 1, vpravo) => triediť druhú polovicu rekurzívne
Zavolajte zlúčenie (Arr, ľavé, stredné, pravé) a zlúčte zoradené polia vo vyššie uvedených krokoch.
Východ

Ako je uvedené vo vyššie uvedenom pseudo kóde, v algoritme zlúčenia triedenia rozdelíme pole na polovicu a každú polovicu triedime rekurzívnym spôsobom spojenia. Keď sú podradné polia zoradené jednotlivo, sú tieto dve podskupiny zlúčené a vytvorí sa kompletné zoradené pole.

Pseudokód na zlúčenie

Nasleduje pseudokód pre techniku ​​zlučovania. Najskôr máme procedúru zlúčenia, ktorá má rekurzívne rozdeliť pole na polovice. Potom máme rutinu zlúčenia, ktorá zlúči zoradené menšie polia, aby sme získali úplné zoradené pole.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a[0] ... a[N/2] var array2 as array = a[N/2+1] ... a[N] array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1[0] > array2[0] ) add array2 [0] to the end of c remove array2 [0] from array2 else add array1 [0] to the end of c remove array1 [0] from array1 end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure

Poďme si teraz na príklade ilustrovať techniku ​​zlučovania.

Ilustrácia

zlúčiť triediť Ilustráciu

Vyššie uvedená ilustrácia môže byť zobrazená vo forme tabuľky nižšie:

PrejditeNetriedený zoznamrozdeliťZoradený zoznam
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
dva{12,23,2,43}
{51,35,19,4}		{12.23} {2.43}
{51,35} {19.4}		{}
3{12.23} {2.43}
{51,35} {19.4}		{12.23} {2.43}
{35,51} {4,19}		{12.23} {2.43}
{35,51} {4,19}
4{12.23} {2.43}
{35,51} {4,19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Ako je znázornené na vyššie uvedenom obrázku, najskôr je pole rozdelené na dve čiastkové polia dĺžky 4. Každé čiastkové pole je ďalej rozdelené na ďalšie dve čiastkové polia dĺžky 2. Každé čiastkové pole je potom ďalej rozdelené na čiastkové pole po jednom prvku. Celý tento proces je procesom „Rozdeľte“.

Akonáhle sme rozdelili pole na čiastkové polia po jednom prvku, musíme teraz tieto polia zlúčiť v zoradenom poradí.

Ako je znázornené na ilustrácii vyššie, vezmeme do úvahy každé čiastkové pole jedného prvku a najskôr prvky skombinujeme a vytvoríme podskupiny dvoch prvkov v zoradenom poradí. Ďalej sú zoradené zoradené podskupiny dĺžky dva a skombinované tak, aby vytvorili dva podskupiny po dĺžke štyri. Potom skombinujeme tieto dve čiastkové polia a vytvoríme úplné zoradené pole.

Iteratívne zlúčenie zoradiť

Algoritmus alebo technika zlučovania, ktorú sme videli vyššie, používa rekurziu. Je tiež známy ako „ rekurzívne zlúčenie “.

Vieme, že rekurzívne funkcie používajú zásobník volaní funkcií na ukladanie prechodného stavu volajúcej funkcie. Ukladá tiež ďalšie informácie o účtovníctve týkajúce sa parametrov atď. A predstavuje réžiu z hľadiska ukladania aktivačného záznamu volania funkcie, ako aj obnovenia vykonávania.

Všetkých týchto réžií sa môžeme zbaviť, ak namiesto rekurzívnych funkcií použijeme iteračné funkcie. Vyššie uvedený algoritmus zlúčenia je možné tiež ľahko previesť na iteračné kroky pomocou slučiek a rozhodovania.

Rovnako ako rekurzívne triedenie zlúčenia, aj iteračné triedenie zlúčenia má zložitosť O (nlogn), a preto je výkonnostný, fungujú navzájom na rovnakej úrovni. Sme jednoducho schopní znížiť réžiu.

V tomto tutoriáli sme sa sústredili na rekurzívne triedenie zlúčenia a ďalej implementujeme rekurzívne triedenie zlúčenia pomocou jazykov C ++ a Java.

Ďalej je uvedená implementácia techniky spojenia pomocou C ++.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray[i]; } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Výkon:

Zadajte počet prvkov, ktoré sa majú triediť: 10

Zadajte 10 prvkov, ktoré sa majú zoradiť: 101 10 2 43 12 54 34 64 89 76

Zoradené pole

2 10 12 34 43 54 64 76 89 101

V tomto programe sme definovali dve funkcie, merge_sort a choď . Vo funkcii merge_sort rozdelíme pole na dve rovnaké polia a na každé z týchto čiastkových polí zavoláme funkciu zlúčenia. Vo funkcii zlúčenia urobíme skutočné triedenie na týchto čiastkových poliach a potom ich zlúčime do jedného úplného zoradeného poľa.

Ďalej implementujeme techniku ​​Merge Sort v jazyku Java.

class MergeSort { void merge(int arr[], int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr[] = new int [left]; int Right_arr[] = new int [right]; for (int i=0; i

Výkon:

Vstupné pole

101 10 2 43 12 54 34 64 89 76

Pole zoradené pomocou zlúčenia

2 10 12 34 43 54 64 76 89 101

Aj v implementácii Java používame rovnakú logiku ako v implementácii C ++.

Zlúčiť triedenie je efektívny spôsob triedenia zoznamov a väčšinou sa používa na triedenie prepojených zoznamov. Pretože používa prístup rozdelenia a dobývania, technika triedenia zlúčenia funguje rovnako efektívne pre menšie aj väčšie polia.

Analýza zložitosti algoritmu triedenia zlúčenia

Vieme, že na to, aby sme mohli uskutočniť radenie pomocou zlúčenia, najskôr rozdelíme pole na dve rovnaké polovice. Toto predstavuje „log n“, čo je logaritmická funkcia a maximálny počet krokov je log (n + 1).

Ďalej nájdeme stredný prvok poľa, ktorý vyžaduje jeden krok, tj. O (1).

Potom, aby sme zlúčili čiastkové polia do poľa n prvkov, vezmeme O (n) množstvo času behu.

Celkový čas na vykonanie zlúčenia bude teda n (log n + 1), čo nám dá časovú zložitosť O (n * logn).

Najhoršia časová zložitosťO (n * log n)
Najlepšia časová zložitosť prípaduO (n * log n)
Priemerná časová zložitosťO (n * log n)
Zložitosť priestoruO (n)

Časová zložitosť pri zlučovaní je rovnaká vo všetkých troch prípadoch (najhoršia, najlepšia a priemerná), pretože vždy rozdeľuje pole na čiastkové polia a potom zlúči čiastkové polia s lineárnym časom.

Zlúčenie zoradenia vždy zaberie rovnaké množstvo priestoru ako netriedené polia. Preto, keď je zoznamom na triedenie pole, zlúčenie by sa nemalo používať pre veľmi veľké polia. Zlúčenie zoradenia je však možné pri triedení prepojených zoznamov využiť efektívnejšie.

Záver

Zlúčiť triedenie používa stratégiu „rozdeľuj a panuj“, ktorá rozdeľuje pole alebo zoznam do mnohých podradených polí a triedi ich jednotlivo a potom sa zlúči do úplného zoradeného poľa.

Zlúčenie zoradenia funguje rýchlejšie ako iné spôsoby triedenia a rovnako efektívne funguje aj pre menšie a väčšie polia.

Viac o rýchlom radení sa dozvieme v našom pripravovanom výučbe!

=> Tu si pozrite pozorne na Sprievodcu školením pre C ++.

Odporúčané čítanie

^