Turinys:
Apibrėžimas - ką reiškia „Quicksort“?
„Quicksort“ yra populiarus rūšiavimo algoritmas, kuris praktikoje dažnai yra greitesnis nei kiti rūšiavimo algoritmai. Jis naudoja „padalijimo ir užkariavimo“ strategiją, kad greitai surūšiuotų duomenų elementus, padaliję didelį masyvą į du mažesnius masyvus. Jį 1960 m. Sukūrė Charlesas Antonijus Richardas Hoare'as (paprastai žinomas kaip CAR Hoare arba Tony Hoare) Nacionalinės fizinės laboratorijos mašininio vertimo projektui.„Techopedia“ paaiškina „Quicksort“
Quicksort yra algoritmas, naudojamas greitai surūšiuoti elementus masyve, nesvarbu, koks masyvo dydis yra. Jis yra gana lengvai keičiamas ir gana gerai veikia mažus ir didelius duomenų rinkinius, lengvai įgyvendinamas ir mažai sudėtingas. Tai atliekama pasidalijimo ir užkariavimo metodu, kuris padalija vieną didelį masyvą į du mažesnius ir tada pakartoja šį procesą visiems sukurtiems masyvams, kol rūšiavimas bus baigtas.
Quicksort algoritmas atliekamas taip:
- Iš masyvo pasirenkamas pasukimo taškas.
- Masyvas pertvarkomas taip, kad visos vertės, mažesnės už šarnyrą, būtų perkeltos prieš jį, o visos vertės, didesnės už šarnyrą, būtų perkeltos po jo, o vertės lygios šerdesui abipusiai. Kai tai bus padaryta, atrama yra galutinėje padėtyje.
- Aukščiau pateiktas žingsnis pakartojamas kiekvienam mažesnių reikšmių poaibiui, taip pat atliekamas atskirai didesnių reikšmių submasteriui.
Tai kartojama tol, kol visas masyvas yra rūšiuojamas.
