Meni

Spoji sortiranje u C ++ s primjerima

merge sort c with examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Tehnika sortiranja spajanja C ++.

Algoritam sortiranja spajanja koristi ' podijeli i osvoji Strategija u kojoj problem dijelimo na podprobleme i te podprobleme rješavamo pojedinačno.

Ti se podproblemi zatim kombiniraju ili spajaju zajedno kako bi se stvorilo jedinstveno rješenje.

=> Ovdje pročitajte popularne serije obuke za C ++.

Spoji sortiranje

Što ćete naučiti:

najbolji program za praćenje procesora

Pregled

Sortiranje spajanja izvodi se pomoću sljedećih koraka:

# 1) Popis koji se sortira podijeljen je u dva polja jednake duljine dijeljenjem popisa na srednjem elementu. Ako je broj elemenata na popisu 0 ili 1, tada se popis smatra sortiranim.

#dva) Svaka se podvrsta sortira pojedinačno pomoću rekurzivnog sortiranja spajanjem.

# 3) Zatim se razvrstani podpopisi kombiniraju ili spajaju u cjelokupni razvrstani popis.

Opći algoritam

Općeniti pseudo-kod za tehniku ​​sortiranja spajanjem dan je u nastavku.

Deklarirajte niz Arr duljine N
Ako je N = 1, Arr je već sortiran
Ako je N> 1,
Lijevo = 0, desno = N-1
Pronađi sredinu = (lijevo + desno) / 2
Pozovite merge_sort (Arr, left, middle) => rekurzivno sortiranje prve polovice
Pozovite merge_sort (Arr, middle + 1, right) => rekurzivno sortiranje druge polovice
Pozovite spajanje (Arr, lijevo, srednje, desno) za spajanje sortiranih nizova u gornjim koracima.
Izlaz

Kao što je prikazano u gornjem pseudo kodu, u algoritmu za sortiranje spajanja dijelimo niz na pola i sortiramo svaku polovicu pomoću rekurzivnog sortiranja spajanjem. Jednom kada se pod-nizovi sortiraju pojedinačno, dva se pod-niza spoje zajedno da tvore cjeloviti razvrstani niz.

Pseudo kôd za sortiranje spajanja

Slijedi pseudo kôd za tehniku ​​sortiranja spajanjem. Prvo, imamo sortiranje postupka spajanja da bismo niz rekurzivno podijelili na polovice. Tada imamo rutinu spajanja koja će spojiti razvrstane manje nizove da bi se dobio cjeloviti razvrstani niz.

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

Ilustrirajmo sada tehniku ​​sortiranja spajanjem na primjeru.

Ilustracija

spajanje sortiraj ilustracija

Gornja ilustracija može se prikazati u tabličnom obliku ispod:

ProćiNesortirani popispodijelitiPoredani popis
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}

Kao što je prikazano u gornjoj predstavi, prvo se niz dijeli na dva podniza duljine 4. Svaki podniz dalje se dijeli na još dva podniza duljine 2. Svaki se podskup dalje dijeli na podnir od po jednog elementa. Cijeli ovaj postupak je postupak 'Podijeli'.

Nakon što smo niz podijelili u podnizove od po jednog elementa, sada ih moramo objediniti poredanim redoslijedom.

Kao što je prikazano na gornjoj ilustraciji, uzimamo u obzir svaki podskup pojedinog elementa i prvo kombiniramo elemente kako bismo oblikovali podnizove dvaju elemenata poredanim redoslijedom. Dalje, razvrstani podnizovi duljine dva razvrstavaju se i kombiniraju u dva podniza duljine po četiri. Zatim kombiniramo ova dva podniza da bismo stvorili cjeloviti sortirani niz.

Iterativno sortiranje spajanja

Algoritam ili tehnika sortiranja spajanja koje smo vidjeli gore koristi rekurziju. Također je poznato kao „ rekurzivno sortiranje '.

Znamo da rekurzivne funkcije koriste stek poziva funkcija za pohranu posrednog stanja funkcije pozivanja. Također pohranjuje ostale knjigovodstvene podatke za parametre itd. I postavlja općenito u smislu pohrane aktivacijskog zapisa poziva funkcije, kao i nastavka izvršavanja.

Svih se ovih općih troškova može riješiti ako koristimo iterativne funkcije umjesto rekurzivnih. Gornji algoritam sortiranja spajanja također se lako može pretvoriti u iterativne korake pomoću petlji i donošenja odluka.

Poput rekurzivnog sortiranja spajanja, iterativno sortiranje stapanja također ima složenost O (nlogn), stoga pametno izvodi performanse, oni se izvode u međusobnom ravan. Jednostavno smo u mogućnosti smanjiti režijske troškove.

U ovom uputstvu koncentrirali smo se na rekurzivno sortiranje spajanja, a zatim ćemo implementirati rekurzivno sortiranje spajanja pomoću jezika C ++ i Java.

Dolje je data implementacija tehnike sortiranja spajanjem pomoću 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<

Izlaz:

Unesite broj elemenata za sortiranje: 10

Unesite 10 elemenata za sortiranje: 101 10 2 43 12 54 34 64 89 76

Sortirani niz

2 10 12 34 43 54 64 76 89 101

U ovom programu definirali smo dvije funkcije, spojiti_razvrstati i ići . U funkciji spajanja_sort, dijelimo niz na dva jednaka niza i pozivamo funkciju spajanja na svakom od ovih podniza. U funkciji spajanja radimo stvarno sortiranje na tim pod nizovima, a zatim ih spajamo u jedan cjeloviti razvrstani niz.

Dalje, implementiramo tehniku ​​sortiranja stapanja na jeziku 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

Izlaz:

Ulazni niz

101 10 2 43 12 54 34 64 89 76

Niz sortiran pomoću sortiranja spajanjem

2 10 12 34 43 54 64 76 89 101

I u implementaciji Jave koristimo istu logiku kao u implementaciji C ++.

Spajanje sortiranja učinkovit je način sortiranja popisa i uglavnom se koristi za sortiranje povezanih popisa. Budući da koristi pristup podijeli i osvoji, tehnika sortiranja spajanjem djeluje jednako učinkovito kako za manje tako i za veće nizove.

Analiza složenosti algoritma sortiranja stapanja

Znamo da da bismo izvršili sortiranje pomoću sortiranja spajanjem, prvo dijelimo niz na dvije jednake polovice. To predstavlja „log n“, što je logaritamska funkcija, a najviše je poduzetih koraka log (n + 1).

Dalje da bismo pronašli srednji element niza potreban nam je jedan korak, tj. O (1).

Tada ćemo za spajanje podnizova u niz od n elemenata uzeti O (n) količinu radnog vremena.

Stoga će ukupno vrijeme za izvođenje sortiranja spajanja biti n (log n + 1), što nam daje vremensku složenost O (n * logn).

Najgora vremenska složenostO (n * log n)
Najbolja vremenska složenostO (n * log n)
Prosječna vremenska složenostO (n * log n)
Složenost prostoraNa)

Složenost vremena za sortiranje spajanja jednaka je u sva tri slučaja (najgora, najbolja i prosječna) jer uvijek dijeli niz na podnizove, a zatim spaja podnizove uzimajući linearno vrijeme.

Sortiranje spajanja uvijek zauzima jednaku količinu prostora kao nerazvrstani nizovi. Stoga, kada je popis koji se sortira niz, sortiranje spajanjem ne bi se trebalo koristiti za vrlo velike nizove. Međutim, sortiranje spajanjem može se učinkovitije koristiti za sortiranje povezanih popisa.

Zaključak

Spajanje sortiranjem koristi strategiju 'podijeli i osvoji' koja polje ili popis dijeli na brojne podskupine i sortira ih pojedinačno, a zatim spaja u cjeloviti sortirani niz.

Spajanje sortiranja izvodi se brže od ostalih metoda sortiranja, a također učinkovito djeluje za manje i veće nizove.

Istražit ćemo više o Brzom sortiranju u našem nadolazećem vodiču!

=> Ovdje pripazite na Vodič za obuku za početnike C ++.

Preporučena literatura

^