Мени

Споји сортирање у Ц ++ са примерима

merge sort c with examples

Техника сортирања обједињавања Ц ++.

Алгоритам сортирања обједињавања користи „ завади па владај Стратегија у којој проблем делимо на подпроблеме и те подпроблеме решавамо појединачно.

Ови подпроблеми се затим комбинују или спајају заједно да би се створило јединствено решење.

=> Овде прочитајте популарне серије обуке за Ц ++.

Сортирање спајањем

Шта ћете научити:

Преглед

Сортирање обједињавања врши се помоћу следећих корака:

# 1) Листа која се сортира подељена је на два низа једнаке дужине дељењем листе на средњем елементу. Ако је број елемената на листи 0 или 1, тада се листа сматра сортираном.

#два) Свака подлистка се сортира појединачно помоћу сортирања спајањем рекурзивно.

# 3) Поређане под-листе се затим комбинују или споје заједно да би се формирала комплетна сортирана листа.

Општи алгоритам

Општи псеудо-код за технику сортирања спајањем дат је у наставку.

најбољи бесплатни софтвер за резервне копије за Виндовс 10 2017

Прогласите низ Арр дужине Н
Ако је Н = 1, Арр је већ сортиран
Ако је Н> 1,
Лево = 0, десно = Н-1
Пронађи средину = (лево + десно) / 2
Позовите мерге_сорт (Арр, лефт, миддле) => рекурзивно сортирање прве половине
Позовите мерге_сорт (Арр, миддле + 1, ригхт) => рекурзивно сортирање друге половине
Позовите спајање (Арр, лефт, миддле, ригхт) за спајање сортираних низова у горњим корацима.
Излаз

Као што је приказано у горњем псеудо коду, у алгоритму за сортирање спајања делимо низ на пола и сортирамо сваку половину помоћу рекурзивног сортирања спајањем. Једном када се под-низови сортирају појединачно, два под-низа се спајају заједно да би се формирао комплетан сортирани низ.

Псеудо код за сортирање спајања

Следи псеудо код за технику сортирања спајањем. Прво, имамо процедуру сортирања спајања да бисмо низ рекурзивно поделили на половине. Тада имамо рутину спајања која ће спојити сортиране мање низове да би се добио комплетан сортирани низ.

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

Хајде да илуструјемо технику сортирања спајањем на примеру.

Илустрација

спајање сортирај илустрација

Горња илустрација може се приказати у табеларном облику испод:

ПассНесортирана листаподелаСортирана листа
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
два{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}

Као што је приказано у горњој представи, прво је низ подељен на два подниза дужине 4. Сваки под низ је даље подељен на још два подниза дужине 2. Сваки под низ је затим даље подељен у под низ по једног елемента. Читав овај процес је поступак „поделе“.

Једном када смо подјелили низ на поднизове од по једног елемента, сада морамо да објединимо те низове у сортираном редоследу.

Као што је приказано на горњој илустрацији, узимамо у обзир сваки низ једног елемента и прво комбинујемо елементе да бисмо формирали поднизове два елемента у сортираном редоследу. Затим се сортирани поднизови дужине два сортирају и комбинују да би се формирали по два подниза дужине по четири. Затим комбинујемо ова два подниза да бисмо формирали комплетан сортирани низ.

Итеративно сортирање спајања

Алгоритам или техника сортирања спајања које смо видели горе користи рекурзију. Такође је познато као „ рекурзивно сортирање спајања ”.

Знамо да рекурзивне функције користе стек позива функција за чување посредног стања функције позивања. Такође чува остале књиговодствене информације за параметре итд. И поставља опште трошкове у смислу чувања активацијског записа позива функције као и наставка извршавања.

Свих ових режијских трошкова може се решити ако користимо итеративне функције уместо рекурзивних. Горњи алгоритам сортирања обједињавања такође се лако може претворити у итеративне кораке користећи петље и доношење одлука.

Попут рекурзивног сортирања спајања, итеративно сортирање стапања такође има сложеност О (нлогн), па стога перформансе паметно изводе у међусобном рангу. Једноставно смо у могућности да смањимо режијске трошкове.

У овом водичу концентрисали смо се на рекурзивно сортирање спајања, а затим ћемо применити рекурзивно сортирање спајања користећи језике Ц ++ и Јава.

Доље је дата примена технике сортирања спајањем помоћу Ц ++.

#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<

Излаз:

Унесите број елемената за сортирање: 10

Унесите 10 елемената за сортирање: 101 10 2 43 12 54 34 64 89 76

Сортирани низ

2 10 12 34 43 54 64 76 89 101

У овом програму смо дефинисали две функције, сортирање спајањем и иди . У функцији мерге_сорт, делимо низ на два једнака низа и позивамо функцију спајања на сваком од ових под низа. У функцији спајања радимо стварно сортирање на овим под низовима, а затим их спајамо у један комплетан сортирани низ.

Даље, имплементирамо технику сортирања стапања на језику Јава.

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

Излаз:

Улазни низ

101 10 2 43 12 54 34 64 89 76

Низ је сортиран помоћу сортирања спајањем

2 10 12 34 43 54 64 76 89 101

И у имплементацији Јаве користимо исту логику као у примени Ц ++.

Сортирање обједињавањем је ефикасан начин сортирања листа и углавном се користи за сортирање повезаних листа. Како користи приступ подели и освоји, техника сортирања спајањем делује подједнако ефикасно како за мање тако и за веће низове.

Анализа сложености алгоритма сортирања стапања

Знамо да да бисмо извршили сортирање помоћу сортирања спајањем, прво поделимо низ на две једнаке половине. Ово је представљено „лог н“, што је логаритамска функција, а број предузетих корака је највише лог (н + 1).

Следеће да бисмо пронашли средњи елемент низа потребан нам је један корак, тј. О (1).

Затим, да бисмо спојили под-низове у низ од н елемената, узећемо О (н) количину радног времена.

Тако ће укупно време за извођење сортирања спајања бити н (лог н + 1), што нам даје временску сложеност О (н * логн).

Најгора временска сложеностО (н * лог н)
Најбоља временска сложеностО (н * лог н)
Просечна временска сложеностО (н * лог н)
Сложеност простораНа)

Сложеност времена за сортирање стапања је иста у сва три случаја (најгора, најбоља и просечна) јер увек дели низ на поднизове, а затим спаја поднизове узимајући линеарно време.

Сортирање обједињавања увек заузима једнаку количину простора као несортирани низови. Дакле, када је листа коју треба сортирати низ, сортирање обједињавањем не би требало користити за врло велике низове. Међутим, сортирање обједињавањем може се ефикасније користити за сортирање повезаних листа.

Закључак

Сортирање обједињавањем користи стратегију „подели и освоји“ која дели низ или списак на бројне под-низове и сортира их појединачно, а затим се спаја у комплетни сортирани низ.

Сортирање обједињавањем изводи се брже од осталих метода сортирања, а такође ефикасно ради и за мање и веће низове.

Истражићемо више о Брзом сортирању у нашем предстојећем водичу!

=> Овде припазите на водич за обуку за почетнике Ц ++.

Препоручено читање

^