Indholdsfortegnelse:
Definition - Hvad betyder Quicksort?
Quicksort er en populær sorteringsalgoritme, der ofte er hurtigere i praksis sammenlignet med andre sorteringsalgoritmer. Den bruger en split-and-conquer-strategi til hurtigt at sortere dataelementer ved at dele en stor matrix i to mindre arrays. Det blev udviklet af Charles Antony Richard Hoare (almindeligvis kendt som CAR Hoare eller Tony Hoare) i 1960 til et projekt om maskinoversættelse til National Physical Laboratory.Techopedia forklarer Quicksort
Quicksort er en algoritme, der bruges til hurtigt at sortere elementer i en matrix, uanset hvor stor matrix er. Det er ret skalerbart og fungerer relativt godt til små og store datasæt og er let at implementere med lidt tidskompleksitet. Det gør dette gennem en divide-and-conquer-metode, der deler en enkelt stor matrix i to mindre, og derefter gentager denne proces for alle oprettede arrays, indtil sorteringen er fuldført.
Quicksort-algoritmen udføres som følger:
- Et drejepunkt vælges fra matrixen.
- Arrayet er omordnet, så alle værdier, der er mindre end pivoten, flyttes før den, og alle værdier, der er større end pivotten, flyttes efter det, med værdier, der svarer til pivoten, der går begge veje. Når dette er gjort, er drejepunktet i sin endelige position.
- Ovenstående trin gentages for hver undergruppe med mindre værdier såvel som udført separat for undergruppen med større værdier.
Dette gentages, indtil hele matrixen er sorteret.
