Quick Sort-algoritmen er en divide-and-conquer-sorteringsalgoritme, der fungerer ved rekursivt at opdele input-arrayet i mindre og mindre subarrays, indtil hver subarray kun indeholder ét element. Algoritmen er hurtig, effektiv og udbredt i datalogi.
Sådan fungerer hurtig sortering:
1. Opdel: Vælg et pivotelement fra arrayet (ofte det sidste element).
2. Partition: Omarranger arrayet, så alle elementer, der er mindre end pivoten, er til venstre for pivoten, og alle elementer, der er større end pivoten, er til højre. Pivotelementet er i sin endelige sorterede position.
3. Gentag: Gentag de to ovenstående trin for venstre og højre underarrays, og nedbryd dem rekursivt, indtil hver underarray kun indeholder ét element.
Eksempel 1:
Overvej arrayet [5, 3, 8, 2, 1, 4].
en. Divide:Vælg det sidste element, 1 som pivot.
b. Skillevæg:
- Omarranger arrayet:[3, 2, 1, 5, 4, 8] (1 er i sin sorterede position).
c. Gentagelse:
- Venstre underarray:[3, 2, 1] (allerede sorteret)
- Højre underarray:[5, 4, 8] (anvend rekursivt Hurtig sortering)
Efter at have anvendt Hurtig sortering på begge underarrays, er det endeligt sorterede array:[1, 2, 3, 4, 5, 8].
Eksempel 2:
Sortering af et større array
Overvej et array [7, 2, 9, 5, 3, 4, 1, 8, 6].
en. Divide:Vælg det sidste element, 6, som pivot.
b. Skillevæg:
- Omarranger arrayet:[2, 5, 3, 4, 1, 7, 9, 6] (6 er i sin sorterede position).
c. Gentagelse:
- Venstre underarray:[2, 5, 3, 4, 1] (anvend rekursivt Hurtig sortering)
- Højre underarray:[7, 9] (allerede sorteret)
Efter at have afsluttet de rekursive opkald er det sorterede array:[1, 2, 3, 4, 5, 6, 7, 8, 9].
Tidskompleksitet:
- Bedste tilfælde:O(n log n)
- Gennemsnitlig tilfælde:O(n log n)
- Worst-Case:O(n^2) (opstår, når arrayet allerede er sorteret eller omvendt sorteret)
Overordnet set tilbyder Quick Sort algoritmen en effektiv sorteringsløsning med en god gennemsnitlig sagstidskompleksitet på O(n log n). Dens enkelhed og alsidighed har gjort den til en populær algoritme til at sortere opgaver på tværs af forskellige programmeringssprog.
