[C#] Arrays - 13 задача


1
13.* Write a program that sorts an array of integers using the merge sort algorithm (find it in Wikipedia).



Отговори



18

http://pastebin.com/V6DHczUd

Малко разяснения, защото задачата е със звездичка.

Решението го разделяме на два отделни метода. Първия разделя масива на два подмасива с равни дължини (или максимално равни, при нечетна дължина), а втория сглобява от два масива един, който е сортиран.

1. Декларираме си масив от числа за вход и изход, който ще отпечатим на конзолата.

2. Декларираме рекурсивен метод MergeSort, който да разделя един масив на два отделни. Края на рекурсията идва, когато дължината на текушия масив е по малък или равен на единица, защото масив от един елемент може да се нарече сортиран.

3. В този метод разделяме на два подмасива left и right текущия масив и извикваме рекурсивно същия този метод още два пъти да раздели и тези left и right, до момент, в който те са останали дълги единица или по-малко. 

4. След това връщаме като стойност следващия метод MergeArrays. Той проверява кой елемент е по-малък от двата разбити масива и ги подрежда по големина в един общ масив.

5. Отпечатваме резултата.


от ivaylo.kenov (30760 точки)


0
Здравей! Искам само да ти кажа, че твоя код доста ми помогна, за да разбера рекурсията като цяло:)

от vlad0 (6103 точки)

0
И аз благодаря! Наистина разбираемо и добре обяснено :)

от naso.003 (430 точки)



7

Ето и моето решение: source.

Класически алгоритъм за разделяй-владей. Заделям допълнителната памет само веднъж. Смятам средата с тази формула, за да не се препълни при големи числа.


от jasssonpet (6814 точки)


0
Както винаги много хубаво и стегнато. Само една молба - наименовай променливите по малко по-ясен начин или алтернативно - слагай коментари, че много трудно иначе човек хваща логиката. Особено като е изкарана основната логика в метод, тогава дори не може да се дебъгне (или поне аз не знам как), че да проследиш какво става.

от AlexPopov (1568 точки)

0
l(eft) е левият индекс, m(iddle) e средата, r(ight) е десният индекс. На merge i е на първия масив, j е на втория масив. В началото се извиква с i = първия елемент, r = последния елемент.
Добавих и малко коментари, надявам се да стане по-ясно.

от jasssonpet (6814 точки)



0
Пробвах и с листи и с масиви.За съжаление на мен ми хвърля StackOverflowException, което е много дразнещо и бих се радвал, ако някой сподели решение на проблема.



0
Извинете намерих си грешка в кода, която е предизвиквала безкрайна рекурсия :)


0
Може да споделиш решението си все пак :)

от Assi.NET (3050 точки)



6

Merge sort

Тъй като се опитах да напиша алгоритъма без методи и се наложи леко да го изменя, ще се радвам да чуя дали според вас това все още е Merge sort алгоритъм :)


от kdikov (3407 точки)


2

Здравейте, тук има схема, която според мен много добре обяснява какво точно прави алгоритъмът.
http://www.codeproject.com/Articles/42068/Merge-Sort

Ето и моето решение:

http://www.telerik-vats.cloudvps.bg/c-ii-част-масиви-13-задача/

Описание:

http://www.telerik-vats.cloudvps.bg/методи-за-сортиране-merge-sort/


от smg_hacker (484 точки)


0
Евала за обяснението! Много чисто и ясно!

от anonymous (0 точки)

0
За масив с четен брой числа, по средата изписва 0 вместо числото което трябва да е там по принцип.

от vasil.emilov (20 точки)


0

от Stefanpu (404 точки)


3

Това е моето решение:

http://it.blogbg.eu/?p=113

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


от krasi.nikolov (1412 точки)


0
Като кликна "Read more" не се отваря никоя от статиите. Не знам дали само при мен е така, но ако искаш го погледни...

от naso.003 (430 точки)

0
Благодаря, поправих го. Не бях забелязал, вчера инсталирах разни неща.

от krasi.nikolov (1412 точки)


0
http://pastebin.com/MczPkubw ;)

от Rokata (397 точки)


0
При сливането ползвам сентинел, което опростява малко кода: http://pastebin.com/36rPxUg6



0
Това е моето решение - http://pastebin.com/T5MN0DTE
Използвам два метода, единият за разделяне на масива, който се извиква рекурсивно, и другият който прави сливането.

от szaekov (155 точки)