Qsort

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

qsort er en funksjon i C-standardbiblioteket som implementerer en polymorfisk sorteringsalgoritme. Den er oppkalt etter en variant av quicksort som ble skrevet av R. S. Scowen for C standardbiblioteket til Unix, selv om C-standarden ikke krever at den skal implementere i quicksort.[1]

Implementasjoner av qsort oppnår polymorfi, evnen til å sortere ulike former for data, ved å hente en funksjonspeker til en treveis sammenligning, så vel som en parameter som spesifiserer størrelsen på individuelle innmatningsobjekter. ISO C-standarden krever at den sammenlignende funksjon implementerer en total orden på elementene I innmatningstabellen.[2]

I Unix versjon 3 (1973) ble algoritmen en del av sorteringsfunksjonen til standardbiblioteket i form av en rutine skrevet i assembler.[3] I UNIX versjon 6 (1975) ble quicksort skrevet i standard K&R C,[1] og i 1983 ble algoritmen omskrevet for Unix-avarten Berkeley Software Distribution.[4] Funksjonen ble i 1989 standardisert i ANSI C.

Referanser[rediger | rediger kilde]

  1. ^ a b Bentley, Jon L.; McIlroy, M. Douglas (1993). «Engineering a sort function». Software—Practice and Experience. 23 (11): 1249–1265. doi:10.1002/spe.4380231105. 
  2. ^ ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.
  3. ^ «qsort(III), from UNIX Programmer's Manual, Third Edition». 
  4. ^ «qsort(III), from UNIX Programmer's Manual, Sixth Edition». 
informatikkstubbDenne informatikkrelaterte artikkelen er foreløpig kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.