jämförelsefunktion

En jämförelsefunktion är en funktion som tar två värden av samma typ och anger deras relativa ordning. Den används framför allt i sorteringsalgoritmer och i datastrukturer där det krävs att element kan jämföras för att bygga ordnade samlingar eller sökstrukturer. Beroende på språk konventionsskillnaden mellan hur resultatet uttrycks varierar: i många språk returneras ett heltal negativt om det första värdet är mindre än det andra, noll om de är lika och positivt om det första är större; i andra sammanhang används ett boolskt värde som indikerar om det första värdet är mindre än det andra.

En jämförelsefunktion bör definiera en tydlig ordning mellan elementen. Om den används för en total sortering bör den uppfylla egenskaper som totalitet, antisymmetri och transitivitet: mellan varje par a och b gäller att antingen a≤b eller b≤a; om a≤b och b≤a då är a lika med b; och om a≤b och b≤c då är a≤c.

Praktiska exempel inkluderar språkets standardbiblioteksfunktioner: i C är en jämförelsefunktion ofta en jämförelsefunktion till qsort som returnerar ett negativt tal, noll eller positivt; i Java används Comparator<T> med metoden compare(o1, o2) som returnerar ett heltal; i Python kan en jämförelsefunktion skapas med functools.cmp_to_key för att användas i sortering där en jämförelse används indirekt via en nyckelfunktion.

Det finns även överväganden som stabilitet hos sortering och behovet av nyckelbaserad jämförelse (key). I praktiken är det viktigt att jämförelsefunktionen är konsekvent och definierad för de datatyper som används, eftersom en inkonsekvent jämförelse leder till felaktiga resultat i sortering och i ordnade datastrukturer.