Hva er Quicksort?

Quicksort er en av de effektive sorteringsalgoritmene. Algoritmen utfører sortering ved å bruke skillet og erobre paradigme. Tenk på en matrise A [1 ... n] av n elementer. Algoritmen deler matrisen A på en indeks q slik at alle elementer i undergruppen som er igjen av indeksen er mindre enn elementet i indeksen q (a [q]), og alle elementene i riktig subarray er større enn a [Q]. Nå sorterer algoritmen rekursivt de to subarrays A [1… Q-1] og en [Q+1 ... n] på plass ved å ringe Quicksort-funksjonen. For å få indeksen Q bruker algoritmen en partisjonsfunksjon.

Partisjonsfunksjonen er en funksjon som tar inn en matrise a [l… u] som input. Her, l er undergrensen, og u er den øvre grensen av matrisen. Algoritmen finner en indeks q slik at alle elementer mindre enn et [q] faller i subarray a [l… Q-1], og alle elementer som er større enn et [q] -fall i subarray a [q+1… u]. Partisjonsfunksjonen oppnår dette ved å bruke et pivotelement og to pekere - Pointer I og Pointer J til matrisen.

Peker J peker på det første elementet i matrisen, og pekeren I blir initialisert som J-1. Funksjonen itererer gjennom matrisen ved hjelp av peker j. For element A [j] kan elementet være større enn pivotelementet eller mindre enn pivotelementet. Hvis elementet er større enn svingelementet, blir pekeren J økt, og peker på neste element. Hvis elementet A [j] er mindre enn pivotelementet, øker vi pekeren I, bytter en [i] og a [j]. Byttingen av elementene hjelper til med å opprettholde pekeren I slik at elementene opp til elementet peker med pekeren I er mindre enn pivotelementet. Som et siste trinn bytter partisjonsfunksjonen pivotelementet med elementet ved indeks I+1, og flytter dermed pivotelementet i riktig posisjon i den partisjonerte matrisen.

Kildekode

Def Partition (arr, LB, UB):
# Det siste elementet i matrisen er tatt
# å være svingelement
pivot_elt = arr [ub-1]
i = lb - 1
for j i rekkevidde (LB, UB):
# Hvis elementet er mindre enn svingelement
Hvis arr [j] # Bytt elementene slik at elementene
# arr [lb… i] er alltid mindre enn pivotelement
i = i + 1
arr [i], arr [j] = arr [j], arr [i]
# Endelig bytte av pivotelementet og arr [i+1]
# for å sette pivotelementet på plass
arr [i+1], arr [ub-1] = arr [ub-1], arr [i+1]
Returner i+1
def Quick_sort (arr, LB, UB):
if (lb# Rekursivt sortering av matrisen
Q = Partisjon (ARR, LB, UB)
arr = quick_sort (arr, lb, q)
arr = quick_sort (arr, q+1, ub)
Returner arr
if __name__ == "__main__":
arr = [3, 7, 9, 2, 5, 0]
n = len (arr)
arr = quick_sort (arr, 0, n)
trykk (ARR)

Best-case tidskompleksiteten til Quicksort er O (n log n). I best case-scenariet, i hver samtale til algoritmen, deler algoritmen problemet i to delproblemer av samme størrelse. Den verste tidskompleksiteten til Quicksort -algoritmen er O (N^2). Dette skjer når partisjonselementet alltid er valgt som det siste elementet, og matrisen er allerede sortert.