Meni

Združi razvrstitev v jeziku C ++ s primeri

  • Glavni
  • Drugo
  • Združi razvrstitev v jeziku C ++ s primeri

merge sort c with examples

Preizkusite Naš Instrument Za Odpravo Težav

Tehnika sortiranja spajanja C ++.

Algoritem za razvrščanje merge uporablja ' deli in osvajaj 'Strategija, pri kateri problem razdelimo na podprobleme in te podprobleme rešujemo posamično.

Ti podproblemi se nato kombinirajo ali združijo v enotno rešitev.

=> Tukaj preberite priljubljeno serijo usposabljanj za C ++.

Združi razvrsti

Kaj se boste naučili:

kako ustvariti junit test primere v javi

Pregled

Razvrščanje združevanja se izvede po naslednjih korakih:

# 1) Seznam, ki ga je treba razvrstiti, je razdeljen na dva enakovredna polja z delitvijo seznama na srednjem elementu. Če je število elementov na seznamu 0 ali 1, se šteje, da je seznam razvrščen.

#two) Vsak podlist je razvrščen posamično z rekurzivnim razvrščanjem po združevanju.

# 3) Razvrščeni podrazredi se nato kombinirajo ali združijo, da tvorijo popoln razvrščen seznam.

Splošni algoritem

Splošna psevdo-koda za tehniko sortiranja spajanja je podana spodaj.

Navedite polje Arr dolžine N
Če je N = 1, je Arr že razvrščen
Če je N> 1,
Levo = 0, desno = N-1
Poiščite sredino = (levo + desno) / 2
Pokliči merge_sort (Arr, left, middle) => prvo polovico razvrsti rekurzivno
Pokliči merge_sort (Arr, sredina + 1, desno) => drugo polovico razvrsti rekurzivno
Pokličite spajanje (Arr, levo, sredino, desno), če želite združiti razvrščene nize v zgornjih korakih.
Izhod

Kot je prikazano v zgornji psevdo-kodi, v algoritmu za razvrščanje združevanja matriko razdelimo na polovico in vsako polovico razvrstimo s pomočjo spajanja z rekurzivnim razvrščanjem. Ko so podnivi razvrščeni posamično, se dva podniva združita skupaj, da tvorita popolno razvrščeno polje.

Psevdo koda za sortiranje spajanja

Sledi psevdo koda za tehniko razvrščanja po združitvi. Najprej imamo razvrščanje postopkov za razdeljevanje matrike na polovice rekurzivno. Nato imamo rutino spajanja, ki bo združila razvrščena manjša polja, da dobimo popolno razvrščeno polje.

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

Zdaj ponazorimo tehniko razvrščanja z združitvijo s primerom.

Ilustracija

spajanje razvrsti Ilustracija

Zgornjo ponazoritev lahko v spodnji tabeli prikažemo:

MimoNerazvrščen seznamdeliRazvrščen seznam
eno{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}

Kot je prikazano v zgornji predstavitvi, je najprej matrika razdeljena na dva podniva dolžine 4. Vsako podnivo je nadalje razdeljeno na še dva podniva dolžine 2. Vsako podnivo je nato nadalje razdeljeno na podnivo vsakega enega elementa. Celoten postopek je postopek 'delitve'.

Ko smo matriko razdelili na podniže posameznih elementov, moramo zdaj te nize združiti v razvrščenem vrstnem redu.

Kot je prikazano na zgornji sliki, upoštevamo vsako podmrežo posameznega elementa in najprej združimo elemente, da tvorijo podniže dveh elementov v razvrščenem vrstnem redu. Nato so razvrščeni podnizi dolžine dva razvrščeni in združeni, da tvorijo dva podniza dolžine štiri. Nato ta dva podniva združimo, da tvorimo popolno razvrščeno polje.

Iterativno združevanje

Algoritem ali tehnika združevanja, ki smo ga videli zgoraj, uporablja rekurzijo. Znano je tudi kot „ rekurzivno razvrščanje '.

Vemo, da rekurzivne funkcije uporabljajo niz klicev funkcij za shranjevanje vmesnega stanja klicne funkcije. Shranjuje tudi druge knjigovodske informacije za parametre itd. In predstavlja režijske stroške v smislu shranjevanja aktivacijskega zapisa klica funkcije in nadaljevanja izvajanja.

Vseh teh splošnih stroškov se lahko znebimo, če namesto rekurzivnih uporabimo ponavljajoče se funkcije. Zgornji algoritem za razvrščanje združitev je mogoče enostavno pretvoriti v iterativne korake z uporabo zank in odločanja.

Tako kot rekurzivno združevanje ima tudi iterativno razvrščanje združevanja zapletenost O (nlogn), zato je zmogljivost pametna in deluje enakomerno. Enostavno lahko znižamo režijske stroške.

V tej vadnici smo se osredotočili na rekurzivno združevanje, nato pa bomo izvedli rekurzivno združevanje z uporabo jezikov C ++ in Java.

Spodaj je predstavljena tehnika razvrščanja z združitvijo z uporabo 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<

Izhod:

Vnesite število elementov za razvrščanje: 10

Vnesite 10 elementov, ki jih želite razvrstiti: 101 10 2 43 12 54 34 64 89 76

Razvrščeno polje

2 10 12 34 43 54 64 76 89 101

V tem programu smo opredelili dve funkciji, merge_sort in pojdi . V funkciji merge_sort matriko razdelimo na dva enaka polja in pokličemo funkcijo spajanja na vsakem od teh podnizov. V funkciji spajanja izvedemo dejansko razvrščanje teh podnizov in jih nato združimo v eno popolno razvrščeno polje.

Nato v jeziku Java implementiramo tehniko Merge Sort.

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

Izhod:

Vhodno polje

101 10 2 43 12 54 34 64 89 76

Polje je razvrščeno z razvrščanjem po združitvi

2 10 12 34 43 54 64 76 89 101

Tudi pri implementaciji Jave uporabljamo isto logiko kot pri implementaciji C ++.

Razvrščanje po združitvah je učinkovit način razvrščanja seznamov in se večinoma uporablja za razvrščanje povezanih seznamov. Tehnika razvrščanja z združitvijo deluje enako učinkovito tako za manjše kot tudi za večje nize.

Analiza kompleksnosti algoritma sortiranja merge

Vemo, da za izvedbo razvrščanja z združevanjem najprej matriko razdelimo na dve enaki polovici. To je predstavljeno z 'log n', ki je logaritmična funkcija, število izvedenih korakov pa je največ log (n + 1).

Nato za iskanje srednjega elementa polja potrebujemo en korak, tj. O (1).

Nato za združitev podnizov v nabor n elementov vzamemo O (n) količino časa delovanja.

Tako bo skupni čas za izvedbo združevanja n (log n + 1), kar nam daje časovno zapletenost O (n * logn).

Najslabša časovna zapletenostO (n * log n)
Najboljša časovna zapletenostO (n * log n)
Povprečna časovna zapletenostO (n * log n)
Zapletenost prostoraO (n)

Časovna zapletenost pri združevanju je v vseh treh primerih enaka (najslabša, najboljša in povprečna), saj matriko vedno razdeli na podniže in nato podmreže združi ob linearnem času.

Razvrščanje združevanja vedno zavzame enako količino prostora kot nerazvrščene matrike. Torej, kadar je seznam, ki ga je treba razvrstiti, matrika, razvrščanja med spajanjem ne bi smeli uporabljati za zelo velike nize. Vendar je mogoče razvrščanje z združitvijo učinkoviteje uporabiti za razvrščanje povezanih seznamov.

Zaključek

Razvrščanje z združitvijo uporablja strategijo »deli in osvoji«, ki razdeli matriko ali seznam na številne podnive in jih razvrsti posamezno ter nato združi v celotno razvrščeno polje.

Razvrščanje z združitvijo deluje hitreje kot druge metode razvrščanja in deluje učinkovito tudi za manjše in večje nize.

Več o hitrem razvrščanju bomo raziskali v naši prihajajoči vadnici!

=> Tukaj bodite pozorni na vodnik za usposabljanje za začetnike C ++.

Priporočeno branje

^