Масиви и алгоритни за сортиране


7

Здравейте колеги,

В една друга тема бях писал, че съм на зор с времето и вече започнах домашите от масивите. Видно е, че от академията искат да ни запознаят с алгоритмите за сортиране на масиви, Някой от тях трудно ги разбирам, но ще се опитам да вникна повече. Нещо което много ми помогна е това и искам да го споделя с вас: 

http://www.sorting-algorithms.com/ - на този сайт е визуализирано как изглеждат различните алгоритми за сортиране от което можете да получите представа как работят и колко са бързи. На мен ми беше много полезно.

Интересно ми е по-кой метод работи вътрешното сортиране в .net. Ако има някой по запознат, ще се радвам да обясни.




Отговори



1
Сега видях, че има доста такива теми, така че въпроса ми остава как работи вътрешния за .нет алгоритъм за сортиране. Друг интересен въпрос е какво означава, че алгоритама е stable/not stable (може би, че не може да се разчита на сто процента на разултата, ако не е стабилен??)

от dimo.petrof (2887 точки)


3
Sort използва различен алгоритъм в зависимост от броя на елементите в масива http://msdn.microsoft.com/en-us/library/system.array.sort(v=vs.110).aspx Погледни array(Sort) надолу в remarks



4

Когато един алгоритъм за сортиране е стабилен, това означава, че той запазва първоначалната подредба на елементи с една и съща стойност. Примерно сортираме със стабилен алгоритъм този масив: 0 5 2 8 1 2

След сортирането трябва да се получи: 0 1 2 2 5 8

Поне това е, което аз успях да разбера по въпроса.


от lostm1nd (846 точки)


0
Точно така е! Като допълнение към коментара на колегата lostm1nd, мога да дам добър пример, който току що прочетох: http://en.wikipedia.org/wiki/Sorting_algorithm Погледни обяснението с подредбата на картите за игра - веднъж ги подреждаме по сила (по ранк) - с какъвто и да е тип алгоритъм, а след това ги подреждаме и по боя, с изпозлване на стабилен алгоритъм, като с него целим картите които запазват местата си след прилагане на втория алгоритъм, всъщност наистина да запазят местата си. Това би помогнало когато сортираме например даден масив по определен ключ (или критерий), а след това искаме да подредим масива и по втори критерий, като обаче запазим подредбата и от първия критерий, ако това е важно за нас. Стана малко пообъркано обяснението ми, но в приемра е обяснено по-добре:)

от jorotz (0 точки)


9

Вграденият Sort метод в .NET използва различни алгоритми в зависимост от броя на елементите и структурата от данни (Array, List, ...)

Примерно за метода Array.Sort<T> Method (T[]):

Ако размера на масива е по-малък от 16 елемента, той използва Insertion sort алгоритъма.

Ако размера превишава 2 * LogN, където N е размера на масива той използва Heapsort алгоритъма.

Ако не е в горните два случая, използва: Quicksort алгоритъма.

За масиви, които се сортират използвайки Heapsort и Quicksort aлгоритмите, в най-лошия случай имат логаритмична сложност (бързо), т.е. правят O(n log n) операции, където N е дължината на масива.

За List<T>.Sort метода е подобно, само сложността е друга: Средно прави O(n log n) операции (бързо), където n e Count, а в най-лошият случай прави, O(n ^ 2) операции, т.е. много бавен.

Информацията по-горе е от официалната документация на MSDN за .NET Framework 4.5, в която пише разлика в сложността на Quicksort при масив и списък (която си е доста голяма) - не си го измислям аз.  :>

Нестабилно сортиране е такова, при което, ако два елемента са еднакви, тяхната подредба не се запазва. В сравнение със стабилното сортиране, наредбата на еднаквите елементи се запазва. По друг начин казано, имаме масив от обекти, които имат две променливи A и B (примерно, име и възраст). Стабилно е такова сортиране, при което ако сортираме масив по A, а след това го сортираме и по B, той остава сортиран и по A.

П.С. Друг добър сайт, който визуализира начина на сортиране на някои алгоритми: http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Поздрави!


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


0
На QuickSorta worst case-a му е n^2 без значение дали е масив, или лист.


0
Напротив, зависи от имплементацията на алгоритъма (за структурата от данни не съм сигурен), за справка документацията на MSDN: http://msdn.microsoft.com/en-us/library/kwx6zbd4(v=vs.110).aspx

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



4

Аз не съм критерии но според мен един добър курс за алгоритми е този които се води в Cursera  - Algorithms на Princeton University от Robert Sedgewick. в моммента няма активен курс и архива не е активен.

Но ако на някои му е интересно на този линк има мирор на курса за различните лекции само е необходимо да си сменяте цифрата в края на линка.

иначе това са лекцията за

какво е bags ques and stacks

mergesort

quicksort

По голямата част от материала е отвъд това което аз поне зная в момента но въвеждащите лекции са доста интересни.

 

 


от petar_nikov (564 точки)


0
Сред първите 3 лекции е quick find и quick union, а малко преди стаковете е binary search. :}

от miroslav.tsakov (1476 точки)