Алгоритъм за сортиране
From Wikipedia, the free encyclopedia
Алгоритъм за сортиране е алгоритъм, който подрежда списък от елементи в определена последователност.[1] Най-използваните подредби са числовите и лексикографските подредби. Ефективните алгоритми за сортиране са важни за оптимизацията на други алгоритми (например алгоритми за търсене, алгоритми за сливане и др.), който изискват входните данни да са сортирани в определена последователност. Често също така е полезно за конкатенизиране (сливане) на данни и за генериране на разбираеми за човек крайни резултати. Формално казано, изходният резултат от алгоритъма за сортиране трябва да задоволява две условия:
- Изходният резултат е в ненамаляваща последователност (всеки елемент не трябва да е по-малък от предходните на базата на очакваната обща подредба);
- Изходният резултат е пермутация (пренаредба) на входните елементи.
От раждането на компютърните науки, алгоритмите за сортиране са били в процес на разработка и развитие. Ефективното решаване на проблеми, които са на пръв поглед прости и познати, се оказва доста по-сложна и трудоемка задача. Например методът на мехурчето за пръв път е бил анализиран през 1956 година. Въпреки че мнозина са смятали проблема за сортиране за решен, нови по-ефективни алгоритми са продължавали да се откриват (например методът на библиотечното сортиране е бил публикуван за първи път през 2006 година). Алгоритмите за сортиране често се представят в началните класове по компютърни науки, където изобилието от алгоритми за решаването на един проблем елегантно показва разнообразието от ключови алгоритмични концепции, като например голямото О, разделяй и владей, структурни данни, случайни алгоритми, най-добър, най-лош и среден случай, компромис време-памет, горна и долна граница.