Komparatorfunksjoner

Komparatorfunksjoner er funksjoner som tar to verdier og angir hvilken av dem som kommer før den andre i en bestemt ordning. Vanligvis returnerer en komparator en verdi som indikerer at første element er mindre enn, likt med eller større enn det andre elementet. I praksis brukes slike funksjoner primært i sortering, søk og andre operasjoner som krever at elementene har en entydig ordning. Mange språk bruker ulike signaturer for komparatorer, men de deler ofte samme grunnleggende idé: å avgjøre rekkefølgen mellom to elementer.

Ulike språk har ulike konvensjoner for hvordan en komparator uttrykkes. I C og C++ er det vanlig at en comparator defineres som en funksjon eller funktor som returnerer om et element er mindre enn et annet (for eksempel en boolsk verdi i C++ som indikerer a < b, eller en treveis funksjon i C som returnerer negativt, nullt eller positivt tall). Java bruker et Comparator-objekt med metoden compare(a, b) som returnerer et negativt heltall, null eller et positivt heltall. I Python var det tidligere cmp-funksjonen i sortering, men nå brukes nøkkelbasert sortering hvor en nøkkel trekkes ut fra hvert element i stedet for en treveis comparator.

For at en komparator skal være nyttig i sortering og datastrukturer, må den oppfylle visse krav, ofte referert til som en strikt svak ordning (strict weak ordering). Dette innebærer at forholdet er transitive (hvis a < b og b < c så er a < c), asymmetrisk i den forstand at ikke a < a, og at likhet i ordningen er konsistent.

Eksempler inkluderer en komparator som sorterer tall etter verdi, eller streng etter lengde, eller objekter etter et bestemt felt som dato eller prioritet. Det er viktig at komparatoren er konsekvent og uten bivirkninger, slik at sorteringsalgoritmer kan stole på ordningen.