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


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



Отговори



10

Ето решение с листове, че не ми се индексираше по масивите, така е по-изчистено:

http://pastebin.com/6u22u9he

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

След щателно прочуване как и защо работи QuickSort в Google, имплементацията е сравнително ясна.

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

2. Декларираме си рекурсивен метод, който ше извършва алгоритъма на QuickSort и ще приема един масив като променлива.

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

- избираме си начален елемент (pivot), който да ни служи за база за сравнение и спрямо него ще разделим текушия лист на две части, по-малки елементи от pivot-a и по-големи елементи от pivot-a. Тези две части ги записваме в два отделни листа - less и greater. Pivot-a не го записваме в нито една от двете части.

3. Създаваме метод ConcatenateArrays, който да приема и свързва трите части (less, pivot, greater) в един лист и да го връща като променлива.

4. Накрая слагаме стойноста, която да връща рекурсивния метод, а тя е ConcatenateArrays(QuickSort(less), pivot, QuickSort(greater). Тоест рекурсията се извиква два пъти.

С други думи разбиваме главния масив на две части спрямо този pivot, по-малки елементи и по-големи. След това всяка една част от тези двете се разбива отново спрямо техен pivot пак на по-малки и по-големи и т.н. докато дължината на разбитите части станат равни или по-малки от единица, където рекурсията започва да се връща обратно и да съединява разбитите части, но в сортиран вид.

Дано съм бил ясен и полезен. :)


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


0
И аз съм го направила с List, но наблъсках всичко в един метод, само принтенето изнесох в отделен. Вероятно не си забелязал, че в задачата се иска да се сортира масив от стрингове, не от числа.

от mary_russ (292 точки)

0
Ами не, разсеяна му работа. Ще го оправя при първа възможност. Благодаря! :)

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



0

Ето го и с масив :) като има една закоментирана част, която принтира постъпково ако някой иска да види.

http://pastebin.com/iZxDKy4c


от ScorpS (1542 точки)


5

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

Използвам случайно число за pivot.


от jasssonpet (6814 точки)


0
Колега, виж че условието на задачата е: "an array of strings". Аз, туку що, го направих за числа недоглеждайки и сега се псувам :)) *facepalm* Хубаво, че реших да видя други решения. :Рр

от Cheesus (272 точки)

0
Да, благодаря за забележката.

от jasssonpet (6814 точки)


8

Edit: Успях най-накрая да завърша разясненията по решението ми: Quick Sort

Избирам pivot-а, като взимам средния елемент от три произволни.

//

Гледам, че масово използвате средния елемент за pivot, което на доста места прочетох, че е сравнително добро решение. Има привърженици и на произволно генериран pivot.

Намерих и един интересен вариант, в който се избират 3 произволни елемента от интервала и се избира за pivot средния от тях.

Избор на първия елемент от интервала в най-общия случай води до worst-case...

Някой открил ли е други варианти за избор на pivot?


от kdikov (3407 точки)


0
http://www.youtube.com/watch?v=y_G9BkAm6B8

от plamen.yovchev (3283 точки)

0
Благодаря много за супер ясното описание. Цяла вечер се опитвам да навържа тия методи и като разгледах твоето решение видях какви глупости правя:) Още веднъж много благодаря! Аз я правя, като всеки път си избирам за pivot първия елемент от списъка. Пак става и е по-лесно.

от marieta (210 точки)



1
http://pastebin.com/bp3BcYc0
Ето едно решение, което вече не съм съвсем сигурен доколко се придържа към метода, ама е нещо подобно. Аз съм се спрял на първия елемент за pivot, колкото и да е неефективно в общия случай. Ще се радвам на забележки, каквито със сигурност има.

от shristoff (747 точки)


0
и аз не съм сигурен, че това е точно този метод, но прилича...с пивот първи елемент. колкото до забележки, виж кода в края на поста ми. направил съм го да е за стрингове, както е по условие, използвам for за цикли, и съм убединил 2та if-а в един, за да няма повторение на код. http://pastebin.com/h2CWkCjX поздрави :)



0

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


от stann1 (1378 точки)


0
Да, но поне като стигнем до алгоритми за сортиране, методи и рекурсия вече ще ги знаеш :).

от svetlinpanov (179 точки)


2
Решение със стрингове и естествено рекурсия: http://pastebin.com/wAhcjf6V



3

от AlexPopov (1568 точки)


0

Здраво!

Да ви кажа тая задача ме запоти яката, при положение че последно съм барал подобни неща преди 6-7 години когато учих Паскал (да живее!)... Та, след няколко часова борба, все едно с Дан Колов, стигнах до някакво решение...

Та на проблема (който очевидно имам) - програмата си прави каквото си иска, понякога сортира масива, друг път мята любимия StackOverflow, май има някаква зависимост когато масива е с повече елементи, но ми се е случвало и при едни и същи стойности и елементи веднъж да работи, веднъж да метне StackOverflow о.О

Ето го и въпросния код http://pastebin.com/WEt0Hqds всякакви предложения/забележки/помощ се приемат, че ще ме е яд да не я подкарам след толкова борба.


от Alexandar (85 точки)


1
Ето го и моето решение:
http://pastebin.com/4QcyZYCF

Между другото в условието не се ли изисква да е масив от стрингове? Понеже ми направи впечатление, че масово се използва int. :)

от lyubjmf (35 точки)