Обяснени алгоритми за сортиране

Алгоритмите за сортиране са набор от инструкции, които вземат масив или списък като вход и подреждат елементите в определен ред.

Сортовете са най-често в числов или под формата на азбучен ред (наречен лексикографски) и могат да бъдат във възходящ (AZ, 0-9) или низходящ (ZA, 9-0) ред.

Защо алгоритмите за сортиране са важни

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

Някои често срещани алгоритми за сортиране

Някои от най-често срещаните алгоритми за сортиране са:

  • Сортиране на избора
  • Сортиране на балончета
  • Сортиране по вмъкване
  • Сливане на сортиране
  • Бързо сортиране
  • Сортиране на купчина
  • Сортиране при броене
  • Сортиране по Radix
  • Сортиране по кофа

Класификация на алгоритъма за сортиране

Алгоритмите за сортиране могат да бъдат категоризирани въз основа на следните параметри:

  1. Въз основа на Брой замени или инверсия Това е броят пъти, когато алгоритъмът разменя елементи, за да сортира входа. Selection Sortизисква минималния брой суапове.
  2. Въз основа на броя на сравненията Това е броят пъти, в които алгоритъмът сравнява елементи, за да сортира входа. Използвайки нотация Big-O, изброените по-горе примери за алгоритъм за сортиране изискват поне O(nlogn)сравнения в най-добрия случай и O(n^2)сравнения в най-лошия случай за повечето изходи.
  3. Въз основа на рекурсия или Quick Sortнерекурсия Някои алгоритми за сортиране, като например , използват рекурсивни техники за сортиране на входа. Други алгоритми за сортиране, като Selection Sortили Insertion Sort, използват нерекурсивни техники. И накрая, някои алгоритми за сортиране, като например Merge Sort, използват както рекурсивни, така и нерекурсивни техники за сортиране на входа.
  4. Въз основа на алгоритмите за сортиране по стабилност се казва, stableче алгоритъмът поддържа относителния ред на елементите с еднакви ключове. С други думи, два еквивалентни елемента остават в същия ред в сортирания изход, както са били във входа.
  5. Insertion sort,, Merge Sortи Bubble Sortса стабилни
  6. Heap Sortи Quick Sortне са стабилни
  7. Въз основа на изискването за допълнително пространство се казва, че алгоритмите за сортиране са, in placeако изискват постоянно O(1)допълнително пространство за сортиране.
  8. Insertion sortи Quick-sortсе in placeсортират, докато преместваме елементите около въртенето и всъщност не използваме отделен масив, което НЕ е случаят при сортиране на сливане, където размерът на входа трябва да бъде разпределен предварително, за да се съхраняват изходните данни по време на сортирането.
  9. Merge Sortе пример за out placeсортиране, тъй като изисква допълнително място в паметта за своите операции.

Най-добрата възможна времева сложност за всяко сортиране въз основа на сравнение

Всеки алгоритъм за сортиране, базиран на сравнение, трябва да направи най-малко nLog2n сравнения, за да сортира входния масив, а сортирането на Heapsort и merge са асимптотично оптимални сортове за сравнение.