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.

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.ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.

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

Referanser

Kategori:C-standardbiblioteket
Kategori:Quicksort