Innholdsfortegnelse:
Definisjon - Hva betyr Quicksort?
Quicksort er en populær sorteringsalgoritme som ofte går raskere i praksis sammenlignet med andre sorteringsalgoritmer. Den bruker en del-og-erobre-strategi for raskt å sortere dataelementer ved å dele et stort utvalg i to mindre matriser. Den ble utviklet av Charles Antony Richard Hoare (ofte kjent som CAR Hoare eller Tony Hoare) i 1960 for et prosjekt om maskinoversettelse for National Physical Laboratory.Techopedia forklarer Quicksort
Quicksort er en algoritme som brukes til å raskt sortere elementer i en matrise uansett hvor stor matrise er. Det er ganske skalerbart og fungerer relativt bra for små og store datasett, og er enkelt å implementere med liten tidskompleksitet. Det gjør dette gjennom en divide-and-conquer-metode som deler en enkelt stor matrise i to mindre og deretter gjentar denne prosessen for alle opprettede matriser til sorteringen er fullført.
Quicksort-algoritmen utføres som følger:
- Et dreiepunkt velges fra matrisen.
- Matrisen omorganiseres slik at alle verdier som er mindre enn pivoten, blir flyttet før den og alle verdiene større enn pivoten blir flyttet etter den, med verdier som tilsvarer at pivoten går uansett. Når dette er gjort, er pivoten i sin endelige stilling.
- Trinnet ovenfor gjentas for hver delgruppe med mindre verdier, og gjøres separat for delgruppen med større verdier.
Dette gjentas til hele arrayet er sortert.
