14.Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).
[C#] Arrays - 14 задача
Отговори
0
Сортиране на низове с Quick Sort кода на Ивайло Кенов, но променен за масиви от низове и лексикографско сравнение на низовете.
Evgenia Hristova (0 точки)
0
извинявай, но погледна ли първо кога е постнат въпроса? :)
относно "преработката", не смятам че е много професионално да набутваш 3 различни проблема в едно решение. Просто получаваш 1.5 и повече пъти код и ползваш също толкова повече ресурси. Ако се постъпваше така, ексела щеше да управлява кафеварката, пък уинампа можеше да е и файъруол.
относно "преработката", не смятам че е много професионално да набутваш 3 различни проблема в едно решение. Просто получаваш 1.5 и повече пъти код и ползваш също толкова повече ресурси. Ако се постъпваше така, ексела щеше да управлява кафеварката, пък уинампа можеше да е и файъруол.
1
0
Ето и моето решение рекурсивно сортиране на съществуващия масив.
за решенито следвах обясненията от това видео:
0
Гледах един готов код, за да си направя решението и само смених типа от int на string и вместо да ползвам цикли ползвам String.Join(). Получавам обаче StackOverflowException и искам да знам къде е грешката. Някой дали може да ми каже?
Поздрави! :)
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-ове. Помисли как да го реализираш.
Но се замислям... ако има 2 еднакви стринга които стават pivot-и... ще изпусне единия .... ще сгафи. Но това не е за това ниво до което сте вие, така че ... не го гледай засега :) Но това прави глупости: result.Add(String.Join(", ", smaller, pivot, bigger)); тъй като smaller и bigger са list-ове, а не просто string-ове. Помисли как да го реализираш.
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)); дава грешен резултат.
това " 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)); дава грешен резултат.
0
Здравейте, колеги,
не успях да напиша кода сам, защото все излизах от границите на QuickSort и се получаваше някакъв странен алгоритъм ... както и да е. Накрая намерих код за QuickSort на C++ , пренаписах кода за C# и имплементирах логиката за string.
Получи се това
0
Прави ти чест това, че признаваш "заимстването" на кода. Въпроса е да разбереш това, което си направил. Надявам се да си го минал в режим дебъг и да си схванал начина на работа на алогритъма.
Макар че не е съвсем по темата, да се изкажа. Начина на избор на pivot-а е един от проблемите при този метод на сортиране, а от него зависи до голяма степен скоростта на изпълнението му. Всеки метод на сортиране има слаби и силни страни. Т.е. ... ако имаш някаква представа за данните, които биха ти се подавали, можеш да избереш метод, който да компенсира недостатъка си. Примерно ако извършваш доста често вмъкване на елементи във вече сортирани преди това данни, може да се очаква че те са горе-долу в някакъв ред. Затова и се приема pivot-а да е в средата. В твоя алгоритъм се взима за pivot последния елемент. Това при случай когато входните данни са "чисто нови" и винаги се почва "от нулата" при създаването на базата данни е ... абе няма голямо значение кой ще е pivot-а, защото данните са разбъркани. Но ако има вероятност данните да са поне малко подредени, избора на последния елемент за pivot обрича този начин да носи името SlowSort... направо го убива. Не е добра практика.
0
