Сортирането на елементи в списък е ежедневна задача и често отнема много време. Терминът сортиране обикновено се отнася до подреждането на елементите в списък във възходящ или низходящ ред въз основа на предварително зададено отношение за поръчка. Сортирането често е предназначено за търсене, което е още една негова основна дейност в обработката на данни. Представете си колко трудно би било да се търси дума в речник, ако думите в него не бяха организирани или сортирани. Това е причината записите в речник да се съхраняват в стандартен азбучен ред. Многобройните задачи и изчисления стават лесно без сортиране. И тук идва картината за сортиране на алгоритми.

Алгоритъмът за сортиране не е нищо друго освен метод за организиране на елементи от списък в конкретен ред, като стойност от най-ниска до най-висока стойност, от най-ниска до най-ниска стойност, увеличаващ се ред, намаляващ ред, азбучен и т.н. Най-често използваните поръчки са числен и лексикографски ред. Алгоритмите често използват сортирането като ключова подпрограма. Има голямо разнообразие от алгоритми за сортиране, използвани във всеки, използващ богат набор от техники. Един такъв популярен, но също толкова мощен алгоритъм, е Divide and Conquer алгоритъм, който е алгоритъм, базиран на многоразклонена рекурсия. Бързо сортиране и обединяване Сортиране са двата често използвани алгоритми, базирани на алгоритъм Разделяне и Конвертиране.

Какво е Бързо Сортиране?

Quick Sort е високоефективен, но ефективен алгоритъм за сортиране, основан на подхода разделяне и завладяване, който е доста подобен на динамичния подход, при който даден проблем е разделен на два или повече подпроблема и след това решаван рекурсивно. Ако размерът на подпроблемите е достатъчно малък, тогава те се решават просто направо без никакви излишни проблеми. Наричан още подредба за размяна на дялове, алгоритъмът за бързо сортиране разделя списъка, който трябва да бъде сортиран на три основни части: 1) Основен елемент (централни елементи), 2) елементи по-малко от въртящия се и 3) елементи по-големи от въртящия се. Самият въртящ елемент се премества между двете групи до крайното му положение и след това БЪРЗО СОРТ се прилага рекурсивно.

Какво е сортиране на сливане?

Merge Sort е още един алгоритъм за сортиране с общо предназначение, базиран на техниката разделяне и завладяване. Това е един от най-уважаваните и популярни алгоритми за сортиране, създаден да се използва ефективно за сортиране на данни, които се съхраняват външно във файл. Той предлага O (n log n) поведение в най-лошия случай, докато използва O (n) допълнително съхранение. Той разделя колекция „A“ на две по-малки колекции, всяка от които след това се сортира. В последната фаза тези две сортирани колекции се обединяват обратно в една колекция с размер n. Това ще бъде сортиран списък. Алгоритъмът е доста бърз и също така е стабилен сорт и е идеално предпочитан за свързани списъци.

Разлика между Бързо сортиране и Сливане Сортиране

Основи

- И двете Сортиране за бързо сортиране и обединяване са алгоритмите за сортиране, базирани на разделяне и завладяване, с един и същ основен принцип - да разделите проблем на два или повече подпроблема и след това да ги рекуртирате рекурсивно. Те обаче се различават по процедурите за сливане и по отношение на изпълнението. Бързото сортиране обикновено е по-добро и по-бързо от другите алгоритми за сортиране, включително Merge Sort, когато става въпрос за малък набор от данни, докато Merge Sort поддържа последователност независимо от типа набори от данни. Бързото сортиране е идеално предпочитано за масиви, докато обединението сортиране е идеално предпочитано за свързани списъци.

Космическа сложност

- Алгоритъмът за сортиране в Бързо сортиране се извършва рекурсивно и всеки рекурсивен разговор изисква място на стека. Не изисква допълнително пространство за сливане, освен едно пространство за памет за сливане. Тъй като това е алгоритъм за сортиране на място, не се изисква допълнително пространство за извършване на сортиране. Всъщност той използва един и същ масив, докато дели и обединява масива. В Merge Sort, от друга страна, има няколко начина за представяне на данни във файл или като масив, така че се нуждаят от такива работни области като под-файлове или масиви със същия размер, които изискват допълнително пространство.

Най-лошият сложен случай

- Най-лошото поведение за Бързо сортиране се случва, когато дялът е небалансиран, което зависи от това кои елементи се използват за дялово разпределение, в този случай алгоритъмът работи асимптотично толкова бавно, колкото сортирането на вмъкване. Най-лошото изпълнение на Quick Sort е O (n2) и се оставя като упражнение. Това обаче може да се избегне, като се избере правилната опорна точка. Най-лошият случай на Сливане на сортове, от друга страна, се случва, когато той трябва да направи максимален брой сравнения. Като се има предвид линейната производителност за сливане, най-лошият случай на сортирането на сливане е O (n log2 n).

производителност

- Въпреки че алгоритмите за бързо сортиране и обединяване на сортиране се основават на подхода разделяне и завладяване за сортиране, те се различават по методите, използвани за извършване на процедурите за разделяне и сливане. За бързо сортиране основната част от работата е да се раздели списъкът на два под-списъка, който се извършва преди сортирането на под-списъците. При сортирането на обединения основната част от работата е да се обединят два под-списъка, които се извършват след сортирането на под-списъците. Merge Sort изисква временен масив за обединяване на два подмасива, докато за Quick Sort не е необходимо допълнително пространство за масив, което го прави по-ефективно пространство от Marge Sort.

Бързо сортиране спрямо сортиране на сливане: сравнителна диаграма

Обобщение на бързото сортиране спрямо сортирането на сливане

Алгоритмите за бързо сортиране и обединяване се базират на подхода за разделяне и завладяване за сортиране. Те обаче се различават по методите, използвани за извършване на процедурите за разделяне и сливане. Те по принцип работят на същия принцип - да разделят проблем на два или повече подпроблема и след това да ги решават рекурсивно. Сравни сортирането е по-ефективно от Бързото сортиране в най-лошия случай, но двете са еднакво ефективни в средния случай. Но Бързото сортиране е по-ефективно в пространството от сортирането на сливане. Така че Бързото сортиране несъмнено е по-бързо и по-добро от сортирането на сливания, но става неефективно в няколко ситуации, например когато става въпрос за сравнения.

Препратки

  • Cormen, Thomas H., et al. Въведение в алгоритмите. Кеймбридж, Масачузетс: MIT Press, 2009. Печат
  • Хайнеман, Джордж Т. и др. Алгоритми накратко. Севастопол, Калифорния: O’Reilly Media, 2016. Печат
  • Махмуд, Хосам М. Сортиране: Теория на разпространението. Hoboken, Ню Джърси: John Wiley & Sons, 2011. Печат
  • Кредит за изображение: https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/500px-Merge_sort_algorithm_diagram.svg.png
  • Кредит за изображение: https://bg.wikipedia.org/wiki/Quicksort#/media/File:Quicksort-diagram.svg