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


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



Отговори



0

Погледни как е направена имплементацията на java на Merge Sort тук --> http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html

Лично аз не разбрах за какво ти трябват списъци ?


от yonchoy (2134 точки)


1

Ето една имплементация на C#, направена с рекурсия.


от d.georgiev.91 (813 точки)


1

Мен лично тази схема много ми помогна да схвана точно как работи MergeSort - алгоритъмът. Ето в този сайт има допълнителни обяснения.

MERGE (A, p, q, r )

1.      n1 ← q − p + 1

2.      n2 ← r − q

3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]

4.      FOR i ← 1 TO n1

5.            DO L[i] ← A[p + i − 1]

6.      FOR j ← 1 TO n2

7.            DO R[j] ← A[q + j ]

8.      L[n1 + 1] ← ∞

9.      R[n2 + 1] ← ∞

10.    i ← 1

11.    j ← 1

12.    FOR k ← p TO r

13.         DO IF L[i ] ≤ R[ j]

14.                THEN A[k] ← L[i]

15.                        i ← i + 1

16.                ELSE A[k] ← R[j]

 

17.                              j ← j + 1

 


от kalbo_17 (2709 точки)


0
Тц - аз тая задача немога да я реша. Изгледах сумати видеа и разбирам на какъв принцип работи самия алгоритъм, но няма шанс да се сетя сам как да напиша кода.
Ще се радвам ако на някой от workshop-овете или упражненията покажем тази задача по детайлно.

от nzhul (3415 точки)


0
И аз бях така. Алгоритъма ясен, не мога да разпиша кода :) Опитай първо да имплементираш за 2, 4, 8, 16 и т.н. елемента - там ще ти е по-лесно.

от Drago (711 точки)

0
http://25.media.tumblr.com/8b2a7dace6ac3a6bd3b45791f9680c40/tumblr_mjulxfU8YK1rlhbu6o1_500.gif Аз съм същия :(

от batebobo (235 точки)



0

@speedyGonzales - със знанията си до момента и така, както си обясних алгоритъма ползването на списъци ми беше най-близко и разбираемо.

@d.georgiev.91 - все още не съм се запознал с рекурсията, но доколкото успях да разбера и в това решение се ползват два допълнителни списъка

@Gabriella Angelova - и тук се дава като идея да се ползват два подмасива. В имплементацията най-долу също ли се ползва рекурсия?


от Drago (711 точки)


0
По принцип в имплементацията на Merge Sort масива се разбива на два масива или списъка и всеки от тези два масива се разбива на още два масива. И така докато всички масиви не се разбият на масиви от по един елемент. След което ги сортираш и Merge-ваш докато отново не получиш един масив от всичките N на брой масива.

от d.georgiev.91 (813 точки)

0
Ами аз го писах по тази схема без рекурсия и се получи сякаш. Пробвах с няколко входа и ми ги сортира правилно. Ето го и кодът ми: http://pastebin.com/zzKmriV8

от kalbo_17 (2709 точки)



3

Един колега беше пуснал много готино сайтче с визуализация на сортиращите алгоритми. Видели сте го може би, но ще си позволя да го пусна и тук, тъй като темата е пак за сортиране, а на мен лично, повече ми става разбираемо като го гледам анимирано. Гледаш кое къде отива и поне на мен ми става доста ясно.

http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Cheers! :)


от CaptCortez (1242 точки)


3

Разгледах предложените решения, но моето мнение, е че те са крайно неефективни като за "сортиращ алгоритъм", заради заделянето на памет за структура от данни на всяко викането на рекурсивния метод.

Лично аз използвах класическия начин за сортиране по метода Merge sort (директно сортиране в подадения масив, без да се създават нови структури от данни и т.н.)

https://gist.github.com/flextry/5899622

Малко разяснение:

1) Метода MergeSort(int[] elements, int[] temp, int left, int right) се вика докато се разцепи масива на по един елемент.

2) След като е изпълнена стъпка 1) се извиква CompareAndSort(int[] elements, int[] temp, int left, int middle, int right), който сравнява тези елементи, сортира ги като ги записва във временния масив.

3) След това елементите от временния масив се прехвърлят в подадения несортиран.

4) Повтарят се стъпките, но после се вика CompareAndSort не с по един елемент, а двойка с по два елемента, сортират се и т.н.


от martin.nikolov (4535 точки)


0
Да, решението ти е класическо, но как все пак илюстрираш, че работи като не отпечатваш резултата никъде?

от anilak (1134 точки)

0
Много се извинявам и благодаря за поправката, добавих и принтирането. :)

от martin.nikolov (4535 точки)


3

Ето видео от курса по "Структурии от данни и алгоритми", който приключи съвсем скоро. Ники обеснява Merge sort.

Видео


от kirov (4821 точки)


0
Ако не ви се гледа цялото видео: http://www.youtube.com/watch?v=gqSfCQneaUs&feature=youtu.be&t=40m48s

от Ivayl3 (485 точки)

0
Аз съм го нагласил, ама карай все пак. :)

от kirov (4821 точки)


0
Аз едно не мога да разбера : примерно имаме масива int[] array = { 1, -4, 6, 4, 7, 3, 9, -2 }; След като разбием масива докато не остане масив от 1 елемент - получаваме масив с елемент 1, и масив с елемент -4.Сортираме ги и получаваме подреден масив : -4,1, след това имаме пак масив от един елемент : 6, и масив от един елемент : 4 , сортираме ги и получаваме втори подреден масив : 4,6.След това сортираме двата сортирани масива в един цял(но къде се пазят двата сортирани в паметта,от къде идват ми е въпроса, и после новият сортиран къде се пази)

от Hachiko (380 точки)


0
В моето решение ползвам първоначалния масив за да пазя сортираните стойности от двата временни подмасива като променям индексите. След това отново изграждаш два масива от първоначалния. По този начин работиш само с 3 масива.

от Drago (711 точки)

0
Call stack на рекурсията пази данните за момента на извикване , така че когато извикаш рекурсия за следващия масив в call stack ще се пази информация за предния :) гледай темата за рекурсия там е обяснено http://www.youtube.com/watch?v=sjE815NySAQ , аз съм гледал тази и в нея го обясняват предполагам че и в по новите записи ще го има

от TeodorTunev (3061 точки)



2

Направил съм 2 рекурсивни варианта на тази задача, с някакъв опит за "визуализация" на работата на програмата.Първия:

https://github.com/TheOldMan66/01.Arrays/blob/master/13.MergeSort/MergeSort.cs

При него се подава входния масив, той се разбива на 2 подмасива, всеки един от тях на още 2 и така докато масива не стане от 1 елемент. После масивите обратно се събират. Недостатъка е че при примерно 16 елемента паметта само за масивите ще е 16 + 2*8 + 4*4 + 8*2+16*1 = 80 елемента.

После (не без помощта на форума :) ) я реализирах като вместо да "цепя" масива" физически се забавлявам само с индексите - пазя начало и край на "виртуален" масив, който всъщност е парче от оригиналния масив:
https://github.com/TheOldMan66/01.Arrays/blob/master/13.MergeSort%20V2/MergeSort.cs

Така спестявам памет и ми е необходим само за кратко един временен масив в който да "сглобя" двете половинки и след като ги върна в оригиналния масив паметта се освобождава.

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


от JulianG (5316 точки)