[C#] Домашно Arrays - 13 Задача - Merge Sort


2
Доста ме измъчи тази задача и бих искал да получа съвети за по-лесно решение.
Моята идея е на всяка стъпка да съзадавам два нови отворени масива, които пълня до достигане края на оригиналния масив или до 2 на степен съответната стъпка намалена с единица - в началото са с 1 елемент, на 2-ра стъпка с 2 елемента и т.н. След това сравнявам нулевите елементи на двата нови масива, като присвоявам по-малката стойност на съответната позиция в оригиналния масив и трия от временния отворен масив. И така до зануляване на един от двата временни отворени масива, след което просто преписвам останалите елементи от ненулевия масив в оригналния масив. Тестовете, които направих ми се сториха успешни. Но може да не съм проверил всичко. Ще се радвам на коментари и както казах, по-горе на съвети за по-лесно и четимо решение.
Ето го самият код: http://pastebin.com/nmUKBHmW



Отговори



2

Тук съм качил решение без рекурсия.

Частта с разделянето на основни елементи според мен при масиви е излишна, защото те така или иначе са си разделени по индекс. Необходима е при разни други ненаредени структури като сет, бег и т.н.

Показал съм с обяснения как става мърджването - на първа итерация по двойки, на втора - по четворки и т.н. Междинните резутати от всяка итерация се запазват в един друг масив, който накрая на итерацията се присвоява на изходния. Използват се само два масива и това е. Ако има нещо неясно - питайте.


от AntonPetrov (654 точки)


0
Може ли да постнеш подобно решение и за Quick sort algorithm?

от Drago (711 точки)

0
тъкмо го пиша :) Ето: http://forums.academy.telerik.com/105499/c%23-part-2-arrays-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0-14-quick-sort

от AntonPetrov (654 точки)


0

Здравейте,

Имам проблем при най-крайните числа в процеса на сортиране и не мога да разбера от къде е проблема. Ето кода, ако някой може да помогне.

http://pastebin.com/waYymEgF

Реших задачата по начина показан тук:

http://www.youtube.com/watch?v=M814OagXWTI

MergeSort всеки път образува лява и дясна матрица с размер половината от цялата матрица. При всяко рекурсивно извикване на MergeSort  цялата матрица става с размера на лявата или дясната подматрица. Така мартицата се разделя на все по-малки парчета, когато се стигне дъното, когато се извиква Merge.

Merge сравнява един по един елементите от лявата с тези от дясната подматрица. Ако даденият елемент е по-малък от съответния в другата матрица, в главната матрица се записва даденият елемент. 

Ако i == half, следващия елемент от главната матрица (к) става j-тия от дясната подматрица в противен случай - от i-тия от лявата. (Имам чувството, че в последната част нещо не е наред)

 




0
Здравей, Доколкото видях алгоритъма просто пропуска последната итерация и мисля че така горе-долу стана http://pastebin.com/EC9PL2uH Промяната е само в метода Merge, и идеята ми е след while цикъла да хване проверката която изпуска само при финалната подредба. Не е супер оптимално решение така че и аз бих се развал някой по-рабиращ от алгоритъма да обясни какво става : ) Поздрави, п.с. по добре тествай варианта на колегата : )

от stanev.plamen (1143 точки)

0
Проблемът ти идва от там, че когато изпразниш единият от двата сравнявани масива не копираш елементите на втория в оригиналния масив. Ето това трябва да работи (оставил съм като коментар част от кода ти за да се ориентираш)
//if (i == half) //{ // aArray[k] = cArray[j]; //} //else //{ // aArray[k] = bArray[i]; //}
} while (i < half) { aArray[k] = bArray[i]; i++; k++; } while (j < n - half) { aArray[k] = cArray[j]; j++; k++; }

от Drago (711 точки)



0

Аз поизчетох каквото успях да разбера от темата и явно нещо ми убягва. Написал съм един код, който след много четене и зор съумях да разбера какво прави, но не мога да го наглася така че да работи ако в масива има нечетна дължина. Когато дължината е четна - всичко е страхотно, когато не е се чупи и не мога да го оправя. Моля за помощ...http://pastebin.com/V1SufYWD


от Gaert (72 точки)


0
За да избегнеш exception - а, може да направиш това: http://pastebin.com/puuFEsFh

от Stefanpu (404 точки)


0
Здравейте колеги. Е няма толкова гаден алгоритъм, схванах му принципа на действие за 10 минути, а 4 дени му пиша кода. Явно без да знаеш рекурсия и методи си е тегава работа. Та в крайна сметка успях да сътворя нещо което и аз не знам как точно работи :D. А ето го и то:
http://pastebin.com/vYEqDkME
Предварително се извинявам на хората които ще се опитат да го разшифроват, дано не Ви се падне "честта" да ми проверявате домашното, че вече и аз не знам кое и за какво съм го писал.
Поздрави Стефан !

от stefan86 (15 точки)


0

Well, the concept for merge sort algorithm need to be understood first.

I found this resource on merge sort which explains the concept with example.


от aaronsmith (0 точки)