Quick Sort-algoritmen er en del-og-hersk-sorteringsalgoritme som fungerer ved å rekursivt partisjonere input-arrayen i mindre og mindre subarrays til hver subarray inneholder bare ett element. Algoritmen er rask, effektiv og mye brukt i informatikk.
Slik fungerer hurtigsortering:
1. Del: Velg et pivotelement fra matrisen (ofte det siste elementet).
2. Partisjon: Omorganiser matrisen slik at alle elementene mindre enn pivoten er til venstre for pivoten, og alle elementene større enn pivoten er til høyre. Pivotelementet er i sin endelige sorterte posisjon.
3. Rekurs: Gjenta de to ovennevnte trinnene for venstre og høyre undergruppe, og del dem rekursivt ned til hver undergruppe inneholder bare ett element.
Eksempel 1:
Tenk på matrisen [5, 3, 8, 2, 1, 4].
en. Divide:Velg det siste elementet, 1 som pivot.
b. Skillevegg:
- Omorganiser matrisen:[3, 2, 1, 5, 4, 8] (1 er i sin sorterte posisjon).
c. Gjentakelse:
- Venstre undergruppe:[3, 2, 1] (allerede sortert)
- Høyre undergruppe:[5, 4, 8] (bruk hurtigsortering rekursivt)
Etter å ha brukt hurtigsortering på begge undermatrisene, er den endelig sorterte matrisen:[1, 2, 3, 4, 5, 8].
Eksempel 2:
Sortering av et større utvalg
Tenk på en matrise [7, 2, 9, 5, 3, 4, 1, 8, 6].
en. Divide:Velg det siste elementet, 6, som pivot.
b. Skillevegg:
- Omorganiser matrisen:[2, 5, 3, 4, 1, 7, 9, 6] (6 er i sin sorterte posisjon).
c. Gjentakelse:
- Venstre undergruppe:[2, 5, 3, 4, 1] (bruk hurtigsortering rekursivt)
- Høyre undergruppe:[7, 9] (allerede sortert)
Etter å ha fullført de rekursive samtalene, er den sorterte matrisen:[1, 2, 3, 4, 5, 6, 7, 8, 9].
Tidskompleksitet:
- Best-case:O(n log n)
- Gjennomsnittlig sak:O(n log n)
- Worst-case:O(n^2) (oppstår når matrisen allerede er sortert eller omvendt sortert)
Totalt sett tilbyr Quick Sort-algoritmen en effektiv sorteringsløsning med en god gjennomsnittlig sakstidskompleksitet på O(n log n). Dens enkelhet og allsidighet har gjort den til en populær algoritme for å sortere oppgaver på tvers av ulike programmeringsspråk.
