Qsort
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
- ^ 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.
- ^ ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.
- ^ «qsort(III), from UNIX Programmer's Manual, Third Edition». Unix Archive.
- ^ «qsort(III), from UNIX Programmer's Manual, Sixth Edition». Unix Archive.