Kā ieviest apvienošanas kārtojumu C ++ ar piemēriem

Kas ir apvienošanas veids? Apvienot šķirošanu ir uz salīdzināšanu balstīts šķirošanas algoritms, kas pieder dalīšanas un iekarošanas kategorijai. Apvienot kārtošanu izmanto, lai kārtotu masīvu, pamatojoties uz dalīšanas un iekarošanas stratēģiju, kas tiks īsi aplūkota šajā ierakstā kopā ar citiem jēdzieniem, piemēram, tā algoritmu ar piemēru. Mēs arī aplūkosim apvienošanās kārtības sarežģītību laikā C ++

Šajā rakstā tiks apskatīti šādi norādījumi,

• Sadaliet un iekarojiet algoritmu
• Izpratne par apvienošanas šķirošanas algoritmu ar piemēru
• Apvienošanas kārtības pseidokods
• Programma C ++ Merge Sort
• Laika sarežģītība sapludināšanas kārtošanai

Turpinot šo rakstu par apvienošanas kārtojumu C ++

Dalīt un iekarot algoritmu

Ja jūs jau esat iepazinies ar quicksort darbību, jūs varētu būt informēts par sadalīšanas un iekarošanas stratēģiju. Dalīt un iekarot ietver trīs galvenos soļus. Lai saprastu šīs darbības, ņemsim vērā masīvu Hello [], kura sākuma indekss ir “a” un beigu indekss “n”, tāpēc mēs varam rakstīt savu masīvu šādi: Sveiki [a & hellip..n]

masīva javascript garums

Dalīt - Sadalīt un iekarot galvenais solis vai galvenais solis ir sadalīt doto problēmu apakšproblēmās vai apakšdaļās. Šeit ir pieļaujams, ka apakšproblēmām jābūt līdzīgām sākotnējai problēmai un mazākām pēc izmēra. Mūsu gadījumā mēs sadalīsim masīvu divās pusēs [a & hellip.m] [m + 1 & hellip..n] m atrodas a un n indeksa vidū

Iekarot - kad esam pabeiguši problēmu sadalīt apakšproblēmās. Mēs šīs apakšproblēmas atrisinām rekursīvi.

Apvienot - šajā solī mēs atbilstošā veidā apvienojam visus mūsu apakšproblēmu risinājumus. Citiem vārdiem sakot, mēs apvienojam 2 dažādus sakārtotus masīvus, lai izveidotu vienu sakārtotu masīvu. Tur mums ir mūsu šķirotais masīvs.

Turpinot šo rakstu par apvienošanas kārtojumu C ++

Apvienošanas šķirošanas algoritma izpratne ar piemēru

Šajā brīdī mēs zinām, kādu pieeju izmantos apvienošanas kārtība. Apskatīsim piemēru un veiksim katru soli no Hello [] nešķirota uz sakārtotu masīvu.
Piemērs - Sveiki [10, 3, 7, 1, 15, 14, 9, 22]

Iepriekš redzamajā attēlā mēs uzskatījām par nešķirotu masīvu un izmantojām apvienošanas kārtojumu, lai iegūtu sakārtotu masīvu. Apskatīsim katru soli un sapratīsim visu algoritmu

1. Pirmkārt, mēs uzskatījām masīvu Sveiki [10, 3, 7, 1, 15, 14, 9, 22] šajā masīvā ir kopā 8 elementi

2. Kā mēs redzējām iepriekš, apvienošanas kārtošana elementu kārtošanai izmanto sadalīšanas un iekarošanas pieeju. Mēs atradām m, kas atrodas mūsu masīva vidū, un sadalījām masīvu no vidus, kur m = (a - n) / 2 'a' ir kreisākā elementa indekss un n ir mūsu masīva labākā elementa indekss .

3. Pēc pirmā sadalījuma mums ir 2 daļas, kas sastāv no 4 elementiem katrā. Apskatīsim pirmo puslaiku [10, 3, 7, 1].

4. Mēs dalām [10, 3, 7, 1] 2 daļās [10, 3] un [7, 1]. Pēc tam mēs tos sadalām tālāk [10], [3], [7], [1]. Turpmāka dalīšana nav iespējama, jo mēs nevaram aprēķināt m. saraksts, kurā ir viens elements, vienmēr tiek uzskatīts par sakārtotu.

5. Kā notiek apvienošanās? Noskaidrosim. Vispirms [10] un [3] tiek salīdzināti un apvienoti augošā secībā [3, 10] tādā pašā veidā, kā mēs iegūstam [1, 7]

6. Pēc tam mēs salīdzinām [3, 10] un [1, 7]. Pēc salīdzināšanas mēs tos sapludinām augošā secībā un iegūstam [1, 3, 7, 10].

7. [15, 14, 9, 2] arī tiek sadalīti un apvienoti līdzīgā veidā, veidojot [9, 14, 15, 22].

8. Pēdējā posmā mēs salīdzinām un apvienojam [15, 14, 9, 2] [9, 14, 15, 22], lai iegūtu mūsu sakārtoto masīvui., [1, 3, 7, 9, 10, 14, 15, 22].

Turpinot šo rakstu par apvienošanas kārtojumu C ++

Apvienošanas kārtības pseidokods

Sāciet, ja esat palicis
Funkcija mergeSort () rekursīvi sauc sevi par mūsu masīva dalīšanu, līdz tas kļūst par vienu elementu, un funkcija apvienot () tiek izmantota sakārtoto masīvu apvienošanai.
  Turpinot šo rakstu par apvienošanas kārtojumu C ++
 Apvienot šķirošanas programmu C ++ 
#include #include #include izmantojot nosaukumvietas std void sapludināšana (int a [], int Firstindex, int m, int Lastindex) // apvieno apakšmasīvus, kas izveidoti, kamēr sadalījums void mergeSort (int a [], int Firstindex, int Lastindex) {ja (Firstindexlielums int Sveiki [izmērs], es cout<<'Enter the elements of the array one by one:n' for(i=0 i>Sveiki, [i] mergeSort (Sveiki, 0, izmērs - 1) cout<<'The Sorted List isn' for(i=0 i
 Izeja- 
Turpinot šo rakstu par apvienošanas kārtojumu C ++
 Laika sarežģītība 
Laika sarežģītība ir svarīgs aspekts, kas jāņem vērā, runājot par algoritmiem. Tiek uzskatīts, ka apvienošanas šķirošana ir ļoti sarežģīta laikā, salīdzinot ar citiem šķirošanas algoritmiem.
Sliktākā darbības laiks - O (n log n) 
Labākais darbības laiks - O (n log n) 
Vidējais darbības laiks - O (n log n)
Ar to mēs esam nonākuši pie šī apvienošanas kārtojuma izveides C ++ rakstā. Ja vēlaties uzzināt vairāk, iepazīstieties ar   Autors: uzticams tiešsaistes mācību uzņēmums Edureka. Edureka Java J2EE un SOA apmācības un sertifikācijas kurss ir paredzēts, lai apmācītu jūs gan galvenajiem, gan uzlabotajiem Java jēdzieniem kopā ar dažādiem Java ietvariem, piemēram, Hibernate & Spring.
 Vai mums ir jautājums? Lūdzu, pieminējiet to šī emuāra komentāru sadaļā, un mēs sazināsimies ar jums pēc iespējas ātrāk.