Брзо сортирање је један од најбољих метода сортирања низа.

Ако програмирате и ваш код надилази писање калкулатора, често ћете наићи или бити суочени са потребом да сортирате одређени низ података. Постоји много начина за сортирање. У овом чланку ћемо анализирати главне од њих и фокусирати се на брзо сортирање.

Брзи концепт сортирања

Брзо сортирање - Куицк Сорт или ксорт. По имену постаје јасно шта је то и зашто. Али ако није јасно, онда ово је алгоритам Брзим сортирањем низа, алгоритам има просечну О (н лог н) ефикасност. Шта то значи? То значи да се просјечно вријеме рада алгоритма повећава дуж исте путање као и граф ове функције. Неки популарни језици имају уграђене библиотеке са овим алгоритмом, што већ указује да је изузетно ефикасан. То су језици као што су Јава, Ц ++, Ц #.

Алгоритам

Брза метода сортирања користи рекурзију и стратегију "Дивиде анд Цонкуер".

1. У низу тражимо одређени елемент подршке, ради једноставности, боље је узети централни елемент, али ако желите радити на оптимизацији, морат ћете испробати различите опције.

2. Са леве стране ослонца се тражи елемент већи од референце, с десне стране, мањи елемент од референце, а онда их замењујемо. Учините то све док максимум на десној страни није мањи од минимума на лијевој страни. Тако се сви мали елементи бацају на почетак, велики - до краја.

3. Рекурзивно примените овај алгоритам на леви и десни део нашег алгоритма одвојено, затим поново и поново, све док не достигнете један елемент или одређени број елемената. Који је то број елемената? Постоји још један начин да се оптимизује овај алгоритам. Када сортирани део постане приближно једнак 8 или 16, он се може обрадити својим уобичајеним сортирањем, на пример, сортом балона. Зато ћемо повећати ефикасност нашег алгоритма он не обрађује мале низове што је брже могуће.

Тако ће се читав низ обрадити и сортирати. Сада ћемо визуелно проучити овај алгоритам.

Брзо сортирање

Да ли је брзо сортирање најбржи алгоритам за сортирање? Дефинитивно не. Сада је све више и више сортирања, у тренутку када је најбрже сортирање Тимсорт, он ради изузетно брзо за матрице које су изворно сортиране другачије. Али не заборавите да је брзи метод сортирања један од најлакших за писање, веома је важан, јер, у правилу, једноставан пројекат захтева само једноставан правопис, а не огроман алгоритам који ви сами не можете написати. Тимсорт такође није најкомпликованији алгоритам, али му наслов најједноставније не засија.

Имплементација алгоритма

Па, стигли смо до "укусног". Погледајмо сада како је имплементиран овај алгоритам. Као што је раније споменуто, није превише компликовано имплементирати, чак и једноставније. Али ми још увек потпуно анализирамо сваку акцију нашег кода, тако да разумете како брзо сортирање функционише.

Наш метод се зове КуицкСорт. Покреће главни алгоритам у којем преносимо матрицу, њен први и последњи елемент. Запамтимо у варијаблама и и к први и посљедњи елемент сортираног сегмента како не бисмо мијењали те варијабле, као што су нам потребне. Затим проверавамо растојање између првог и последњег провереног: да ли је веће или једнако једном? Ако не, онда смо дошли у центар и морамо да изађемо из сортирања овог сегмента, и ако је тако, настављамо са сортирањем.

Затим узимамо први елемент у сегменту који се сортира за потпорни елемент. Радимо следећи циклус док не стигнемо до центра. У њој радимо још два циклуса: први је за леви део, а други за десни. Ми их изводимо све док постоје елементи који одговарају услову, или док не дођемо до елемента подршке. Затим, ако је минимални елемент још увек десно, а максимум лево, замените их. Када се циклус заврши, промените први елемент и референцу, ако је референца мања. Онда рекурзивно направимо наш алгоритам за десни и леви део поља, и тако наставимо док не достигнемо сегмент од 1 елемента дужине. Онда ће се сви наши рекурзивни алгоритми вратити, и ми ћемо у потпуности напустити сортирање. Такође, на дну се налази метода замене - прилично стандардна метода приликом сортирања низа замена. Да не бисмо писали замену елемената неколико пута, пишемо једном и мењамо елементе у овом низу.

У закључку, можемо рећи да је у погледу односа квалитета и сложености, брзо сортирање на водећој позицији међу свим алгоритмима, тако да дефинитивно треба узети у обзир метод и користити га ако је потребно у вашим пројектима.