sortering

Sortering är processen att ordna en samling objekt enligt ett definierat ordningsmått, vanligtvis i stigande eller fallande ordning. Inom datavetenskap används sortering för att göra data lättare att söka, jämföra och analysera. En sorterad lista möjliggör ofta snabbare sökningar och förenklar vidare bearbetning såsom gruppering, sammanslagning och filtrering.

Sortering kan delas upp i jämförande sorter och icke-jämförande sorter. Jämförande sorter bygger på att jämföra två objekt för att avgöra deras relativa ordning. Icke-jämförande sortering utnyttjar kunskap om dataegenskaper, till exempel olika värdemängder eller digitpositioner, för att ordna objekt utan att göra direkta jämförelser mellan alla par.

Vanliga algoritmer inkluderar jämförande sorter som snabbsort (quicksort), mergesort, heapsort, insättningssortering (insertion sort), urvalssortering (selection sort) och bubblsortering. Mer avancerade jämförande sorter kan uppnå god prestanda i praktiken, men vissa har sämre värsta fall-prestanda utan tilräckliga garantier. Icke-jämförande sorter som räkningssortering (counting sort), bucket sort och radix sort nyttjar kända egenskaper hos data och kan uppnå linjär tid under rätt förutsättningar, men är ofta begränsade till specifika typer av data.

Egenskaper som stabilitet (om lika objekt behåller sin ordning) och platskrav (minne som används) är viktiga när sortering används som del av större processer. Vissa algoritmer är in-symmetriska och kräver extra minne, medan andra arbetar in-place.

Användningsområden inkluderar databassökning, förberedelse av listor före sökningar eller sammanställningar, sortering av filer i datorer och hantering av stora dataset genom extern sortering när data inte får rymmas i minnet.