Функционален подход за selection sort


1

Its me again .. duh! Та, този път си цъках Selection sort и нещо не ми стана ясно защо логиката ми е грешна...(имайки предвид , че не всички тестове ми минават).

https://gist.github.com/kuskmen/026b2a41ecef9a8f83d2571a18a91a5e

Потърсих малко по функционален подход, do not rage.

Нали това беше идеята на selection sort?




Отговори



0

IndexOf винаги ти стартира от 0, което значи че ако имаш масив: 3 3 4 2 1 ще се сортира така:

1 3 4 2 3 (i = 0)

1 2 4 3 3 (i = 1)

1 2 3 4 3 (i = 2)

1 2 3 3 3 (i = 3) тук IndexOf стига до първата 3ка и получаваш нейният индекс (2) и става Swap(arr, 3, 2) и 4-ката се заменя от 3ката преди нея 

Решението е IndexOf да започва от index-a до където си стигнал:

Swap(A, i, Array.IndexOf(A, A.Skip(i).Min(), i));

Можеш да засечеш подобни проблеми ако си дефинираш променлива: int min = A.Skip(i).Min() и провериш стойността й, или сложиш brake point във началото на Swap метода .


от kidroca (1498 точки)


0
Не знам , защо си мислех , че A.Skip(i).Min() всеки път ще ми връща масив стартиращ от индекс i до края ... това ме подведе. Иначе благодаря много за разяснението.


0

Правилно, A.Skip(i) ти връща остатъкът от масива, след това .Min() намира най - малката стойност в остатъка, след това IndexOf търси от ляво на дясно тази най малка стойност само че във оригиналният масив и започваше от 0. 

Можеш да напишеш extension method  за колекции подобен на .Min(), но вместо стойността да връща индекса на който се намира. Така ще е по оптимално.

Swap(A, i, A.IndexOfMin(i));

Където indexOfMin(i) ще връща индекса на най- малката стойност надясно от i.


от kidroca (1498 точки)