Video: Week 4 2024
Her finder du ud af, hvordan en af de mest anvendte sorteringsteknikker i Java faktisk fungerer. Denne teknik kaldes Quicksort, , og det er en meget genial brug af rekursion.
For de fleste af os finder vi ud af, hvordan sorteringsalgoritmer som Quicksort-arbejde kun er en intellektuel øvelse. Java API'en har allerede indbygget sortering.
Quicksort-teknikken sorterer en række værdier ved hjælp af rekursion. Dets grundlæggende trin er således:
-
Vælg en vilkårlig værdi, der ligger inden for rækkevidden af værdier i arrayet.
Denne værdi er pivot punkt . Den mest almindelige måde at vælge pivot punkt på er at vælge den første værdi i arrayet. Folk har skrevet ph.d.-grader på mere sofistikerede måder at vælge et pivot punkt, der resulterer i hurtigere sortering. Stick med at bruge det første element i arrayet.
-
Omregistrer værdierne i arrayet, så alle værdier, der er mindre end drejepunktet, er på venstre side af arrayet, og alle værdier, der er større end eller lig med drejepunktet, er på højre side af array.
Den pivotværdi angiver grænsen mellem venstre og højre side af arrayet. Det er nok ikke dødsted, men det betyder ikke noget. Dette trin kaldes partitionering, og venstre og højre side af arrayerne er partitioner.
-
Behandl nu hver af de to sektioner af arrayet som et separat array, og start over med trin 1 for den sektion.
Det er den rekursive del af algoritmen.
Den hårdeste del af Quicksort-algoritmen er partitioneringstrinnet, som skal omarrangere partitionen, så alle værdier, der er mindre end drejepunktet, er til venstre og alle elementer, der er større end drejepunktet punkt er til højre. Antag, at arrayet har disse ti værdier:
38 17 58 22 69 31 88 28 86 12
Her er pivotpunktet 38, og opgavet for opdelingstrinnet er at omarrangere arrayet til noget som dette: < 17 12 22 28 31 38 88 69 86 58
Bemærk, at værdierne stadig ikke er i orden. Opstillingen er imidlertid blevet opdelt omkring værdien 38: Alle værdier, der er mindre end 38, er til venstre for 38, og alle værdier, der er større end 38, er til højre for 38.
Nu kan du opdele array i to partitioner ved værdien 38 og gentag processen for hver side. Drejeværdien selv går med venstre partition, så den venstre partition er denne:
17 12 22 28 31 38
Denne partition vælger partitionstrinnet 17 som drejepunkt og omorganiserer elementerne som følger: > 12 17 22 28 31 38
Som du kan se, er denne del af arrayet sorteret nu.Desværre er Quicksort ikke klar over, at på dette tidspunkt, så tager det nogle få rekursioner helt sikkert. Men det er den grundlæggende proces.
