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


1
14.Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).



Отговори



0

http://pastebin.com/dKr2kpmV

Сортиране на низове с Quick Sort кода на Ивайло Кенов, но променен за масиви от низове и лексикографско сравнение на низовете. 


от Evgenia Hristova (0 точки)


0
извинявай, но погледна ли първо кога е постнат въпроса? :)
относно "преработката", не смятам че е много професионално да набутваш 3 различни проблема в едно решение. Просто получаваш 1.5 и повече пъти код и ползваш също толкова повече ресурси. Ако се постъпваше така, ексела щеше да управлява кафеварката, пък уинампа можеше да е и файъруол.

от redOne (0 точки)


1
http://pastebin.com/PtzZCX2A
Ето едно решение от мен. Мисля че работи коректно. Приемам критики ако има нещо грешно по кода!!!

от DinkoK (159 точки)


0
Сигурен ли си че това е quick sort ?!?

от Sir_EFO (733 точки)


0

Ето и моето решение  рекурсивно сортиране на съществуващия масив.

http://pastebin.com/BQUtcP3T

 

за решенито следвах обясненията от това видео:

QuickSort


от petar_nikov (564 точки)


0

Гледах един готов код, за да си направя решението и само смених типа от int на string и вместо да ползвам цикли ползвам String.Join(). Получавам обаче StackOverflowException и искам да знам къде е грешката. Някой дали може да ми каже?

http://pastebin.com/rfNdXXjg

Поздрави! :)


от ADimanova (548 точки)


0
При въртене на цикъла pivot-а не трябва да влиза в никой от двата list-а,тъй като ти ръчно го добавяш между тях при слепването. Примерно така: for (int i = 0; i < arrayToSort.Count; i++) { if (String.Compare(arrayToSort[i], pivot) < 0) { smaller.Add(arrayToSort[i]); } else if (String.Compare(arrayToSort[i], pivot) > 0) { bigger.Add(arrayToSort[i]); } }
Но се замислям... ако има 2 еднакви стринга които стават pivot-и... ще изпусне единия .... ще сгафи. Но това не е за това ниво до което сте вие, така че ... не го гледай засега :) Но това прави глупости: result.Add(String.Join(", ", smaller, pivot, bigger)); тъй като smaller и bigger са list-ове, а не просто string-ове. Помисли как да го реализираш.

от JulianG (5316 точки)

0
Здравей,
това " if (i != arrayToSort.Count) " трябва да се смени с " if (i != arrayToSort.Count / 2) ", за да не включваш в smaller самия pivot.
Иначе сега pivot-a се добавя към smaller и при някои случаи не може да се стигне дъното(края) на рекурсията, защото smaller няма да изпълни условието: if (arrayToSort.Count <= 1) и се зацикля.
Също така в метод Concatenate: това: result.Add(String.Join(", ", smaller, pivot, bigger)); дава грешен резултат.

от dob_sal (25 точки)


0

Здравейте, колеги,
не успях да напиша кода сам, защото все излизах от границите на QuickSort и се получаваше някакъв странен алгоритъм ... както и да е. Накрая намерих код за QuickSort на C++ , пренаписах кода за C# и имплементирах логиката за string.
Получи се това

 




0
Прави ти чест това, че признаваш "заимстването" на кода. Въпроса е да разбереш това, което си направил. Надявам се да си го минал в режим дебъг и да си схванал начина на работа на алогритъма. Макар че не е съвсем по темата, да се изкажа. Начина на избор на pivot-а е един от проблемите при този метод на сортиране, а от него зависи до голяма степен скоростта на изпълнението му. Всеки метод на сортиране има слаби и силни страни. Т.е. ... ако имаш някаква представа за данните, които биха ти се подавали, можеш да избереш метод, който да компенсира недостатъка си. Примерно ако извършваш доста често вмъкване на елементи във вече сортирани преди това данни, може да се очаква че те са горе-долу в някакъв ред. Затова и се приема pivot-а да е в средата. В твоя алгоритъм се взима за pivot последния елемент. Това при случай когато входните данни са "чисто нови" и винаги се почва "от нулата" при създаването на базата данни е ... абе няма голямо значение кой ще е pivot-а, защото данните са разбъркани. Но ако има вероятност данните да са поне малко подредени, избора на последния елемент за pivot обрича този начин да носи името SlowSort... направо го убива. Не е добра практика.

от JulianG (5316 точки)


0

Решението е с рекурсия, и генерира случайни числа за масива. http://pastebin.com/TyFhidYT