Бързото сортиране е един от най-добрите методи за сортиране на масиви.

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

Бързо сортиране

Бързо сортиране - Бързо сортиране или сортиране. По име става ясно какво е то и защо. Но ако не е ясно, тогава това е алгоритъм Чрез бързо сортиране на масива алгоритъмът има средна ефективност O (n log n). Какво означава това? Това означава, че средното време на работа на алгоритъма се увеличава по същата траектория като графиката на тази функция. Някои популярни езици имат вградени библиотеки с този алгоритъм и това вече показва, че той е изключително ефективен. Това са езици като Java, C ++, C #.

Алгоритъмът

Методът за бързо сортиране използва рекурсия и стратегията "Разделяй и владей".

1. В масива търсим определен елемент за поддръжка, за по-простота е по-добре да вземем централния, но ако искате да работите по оптимизацията, ще трябва да опитате различни опции.

2. Отляво на опората се търси елемент, по-голям от референтния, отдясно, по-малък елемент от референтния, след което ги разменяме. Направете това, докато максимумът отдясно е по-малък от минимума отляво. По този начин всички малки елементи се хвърлят в началото, големи - до края.

3. Рекурсивно прилагайте този алгоритъм към лявата и дясната част на нашия алгоритъм поотделно, след това отново и отново, докато достигнете до един елемент или определен брой елементи. Какъв е този брой елементи? Има и друг начин за оптимизиране на този алгоритъм. Когато сортираната част стане приблизително равна на 8 или 16, тя може да бъде обработена чрез обичайното си сортиране, например сортиране на балончета. Затова ще увеличим ефективността на нашия алгоритъм, тъй като не обработва малки масиви толкова бързо, колкото бихме искали.

По този начин целият масив ще бъде обработен и сортиран. И сега ще визуализираме визуално този алгоритъм.

Бърза ефективност на сортирането

Бързото сортиране на най-бързия алгоритъм за сортиране? Определено не. Сега има повече и повече сортировки, в момента най-бързото сортиране е Timsort, работи изключително бързо за масиви, които първоначално са били сортирани по различен начин. Но не забравяйте, че бързият метод на сортиране е един от най-лесните за писане, той е много важен, защото, обикновено, един прост проект изисква просто обикновен правопис, а не един огромен алгоритъм, който вие сами не можете да напишете. Timsort също не е най-сложният алгоритъм, но заглавието на най-простия не му хвърля светлина.

Изпълнение на алгоритъм

Е, стигнахме до „вкусното“. Сега нека да разгледаме как този алгоритъм се прилага. Както беше споменато по-рано, не е твърде сложно да се приложи, а дори и просто. Но ние все още напълно анализираме всяко действие на нашия код, така че да разберете как работи бързото сортиране.

Нашият метод се нарича quickSort. Той изпълнява основния алгоритъм, в който прехвърляме масива, неговите първи и последни елементи. Запаметяваме в променливите i и k първия и последния елемент на сортирания сегмент, за да не променяме тези променливи, както ни е необходимо. След това проверяваме разстоянието между първата и последната проверка: тя е по-голяма или равна на единица? Ако не, тогава стигнахме до центъра и трябва да излезем от сортирането на този сегмент и ако е така, ние продължаваме да сортираме.

След това вземаме първия елемент в сегмента, който се сортира за поддържащия елемент. Ще направим следващия цикъл, докато стигнем до центъра. В него правим още два цикъла: първият е за лявата, а вторият за дясната. Ние ги изпълняваме, докато има елементи, които отговарят на условието, или докато достигнем елемента на подкрепа. След това, ако минималният елемент е все още отдясно, а максимумът е отляво, сменете ги. Когато цикълът завърши, променете първия елемент и препратката, ако препратката е по-малка. След това рекурсивно правим нашия алгоритъм за дясната и лявата част на масива, и така продължаваме, докато достигнем сегмент от 1 елемент в дължина. Тогава всички наши рекурсивни алгоритми ще се върнат и ще излезем напълно от сортирането. Също така на дъното има метод на суап - доста стандартен метод при сортиране на масив от заместители. За да не пишем заместването на елементи няколко пъти, пишем веднъж и променяме елементите в този масив.

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