Vergelijkingssortering

Vergelijkingssortering is een klasse van sorteeralgoritmen waarbij de volgorde van de elementen uitsluitend wordt bepaald door vergelijkingen tussen paren elementen. Met andere woorden, de algoritmen beslissen of een element vóór of na een ander element komt op basis van vergelijkingen. Algoritmen die uitsluitend op basis van vergelijkingen werken, worden gezien als onderdeel van deze categorie; methoden die aanvullende informatie over waarden gebruiken (zoals telling of radix-sorters) vallen hier niet onder.

In de theoretische analyse wordt het model van vergelijken gebruikt. Voor n verschillende elementen geldt dat in het slechtste geval minimaal Omega(n log n) vergelijkingen nodig zijn om te sorteren. Dit theoretische lagere bound wordt bereikt door algoritmen als mergesort en heapsort, die beide in O(n log n) vergelijkingen werken. Quicksort heeft gemiddeld O(n log n) vergelijkingen, maar kan in het slechtste geval O(n^2) zijn. Het precieze aantal vergelijkingen hangt af van de input en de implementatie.

Eigenschappen van vergelijking-sorteringen variëren per algoritme. Stabiliteit is een relevante eigenschap: stabiele sorteringen behouden de relatieve volgorde van gelijke elementen, maar dit is niet verplicht bij alle vergelijkingssorteringen. In-place uitvoer is ook afhankelijk van het algoritme: sommige, zoals heapsort, zijn in-place en gebruiken weinig extra geheugen, terwijl andere zoals mergesort extra buffer nodig hebben. Overzichtelijk zijn eenvoudige, maar minder efficiënte vergelijking-sorteringen zoals insertion sort en selection sort, die vaak O(n^2) tijd complexiteit hebben voor grote inputs.

Praktisch gezien kiezen programmeurs een vergelijking-sortering op basis van gewenste tijdspreiding, geheugenbehoefte en stabiliteit, vooral wanneer de ordening uitsluitend via vergelijkingen kan worden bepaald.