Sorteren

Sorteren kan betekenen het indelen van items in groepen of het rangschikken in volgorde volgens een gekozen sorteersleutel met een bijbehorende ordening, vaak een totale orde, zoals stijgend bij getallen of op alfabetische volgorde bij woorden. Bij elke ordening is er een bijbehorende tegengestelde ordening, welke niet zozeer als een aparte ordening wordt beschouwd: de twee zijn met de toevoeging 'oplopend' of 'aflopend' te onderscheiden.

Het kan gaan om werkelijke voorwerpen die bij elkaar worden ingedeeld, bijvoorbeeld in stapels, verpakking of vakken of om gegevens, die in een computer zijn opgeslagen. Bij gegevens helpt de computer bij het sorteren door het toepassen van een sorteeralgoritme. De gegevens kunnen bijvoorbeeld geplaatst zijn in een spreadsheet, een regel per item, waarbij de waarden van de sorteersleutel in een kolom staan, maar de sorteervolgorde kan ook op meer kolommen gebaseerd zijn. Bij spreadsheets is zo'n sorteeralgoritme ingebouwd.

Indelen naar soort en sorteren op basis van een sorteersleutel corresponderen in zoverre met elkaar, dat de sorteersleutel kan worden beschouwd als een middel om de soort te bepalen. Het verschil is dan dat bij een sorteersleutel ook voor de soorten onderling een volgorde is gedefinieerd. Als het aantal soorten klein is, is het, behalve bij zware voorwerpen, maar een kleine stap van indelen naar soort naar het rangschikken in volgorde. Als van de meeste items de waarde van de sorteersleutel verschillend is, is het indelen in groepen van gelijke waarde slechts een bijkomstigheid van sorteren in volgorde, en is het indelen in groepen van een interval van waarden, in combinatie met het sorteren in volgorde van de groepen onderling, een beperkte vorm van sorteren in volgorde van waarde. Als een sorteeralgoritme beschikbaar is, zoals in een spreadsheet, kan dit ook gebruikt worden voor het indelen in groepen.

Bij het sorteren van een multiset van bijvoorbeeld de getallen 2, 1, 2, 3 in oplopende volgorde, krijgt men het unieke resultaat 1, 2, 2, 3. Een multiset van vier voorwerpen waarvan er twee identiek zijn, en in een gegeven beginpositie staat, kan men op basis van een totale ordening van de drie soorten in principe in twee volgordes plaatsen, die zijn te onderscheiden op basis van de verplaatsingen in het sorteerproces. Het verschil tussen de twee eindstanden is per saldo een verwisseling van de twee voorwerpen, maar niet in het resultaat.

Bij een gegeven rij items is een bijbehorende stabiel gesorteerde rij items zodanig dat items die dezelfde sorteersleutel hebben in beide rijen onderling in dezelfde volgorde staan. Bij voorwerpen waarvan sommige identiek zijn kan men dan nog twee soorten stabiliteit onderscheiden, in de strikte versie blijven ook identieke voorwerpen in dezelfde onderlinge volgorde staan.

Gesorteerd kunnen bijvoorbeeld worden ideeën, getallen, eigenschappen, zoals op kleur, dieren, planten, woorden of gevoelens. Het criterium kan ook gevarieerd zijn, bijvoorbeeld sorteren volgens grootte, ouderdom, dikte, hardheid, lichtgevoeligheid, politieke overtuiging, herkomst, inkomen, intelligentie, smeltpunt of haarkleur.

Sorteren wordt vaak voorafgegaan door een vorm van meten en classificeren, maar dit kan ook tegelijk met het sorteren worden gedaan. Bij het sorteren op volgorde worden de waarden van de sorteersleutel meermalen gebruikt, dus als de moeite van het meten of classificeren niet is te verwaarlozen vergeleken met het verplaatsen, is het efficiënt om het resultaat te registreren, bijvoorbeeld door het labelen van de objecten. Bij visueel sorteren op grootte gaat het verplaatsen steeds hand in hand met het beoordelen welke van twee objecten het grootst is, bij elkaar gehouden is dit gemakkelijker.

Als gegevens worden gepresenteerd in een volgorde op basis van een sorteersleutel maken de waarden van de sorteersleutel vaak, maar niet altijd, deel uit van de gepresenteerde waarden. Bij bijvoorbeeld lemma's in een papieren woordenboek worden de lemma's alfabetisch gesorteerd op hun titels en staan die titels ook prominent aan het begin van het lemma. Anderzijds kan bijvoorbeeld een lijst van landen op oppervlakte gesorteerd zijn zonder dat die oppervlakte erbij vermeld wordt. In het eerste geval is een item in de lijst waarvan men de waarde van de sorteersleutel kent veel gemakkelijker te vinden in de lijst, met bijvoorbeeld bisectie, met een zoektijd evenredig met de logaritme van het aantal items in de lijst, terwijl men in het andere geval lineair moet zoeken, met een zoektijd evenredig met het aantal items, tenzij men de waarden van de sorteersleutel voor veel items bij benadering weet, zodat men toch min of meer door middel van bisectie kan zoeken. Als de waarden van de sorteersleutel deel uitmaken van de gepresenteerde gegevens kan men ook bij het bekijken van fragmenten van de lijst op ieder moment gemakkelijk aan de gegevens zien wat op dat moment de sorteersleutel en -volgorde, op- of aflopend, is.

Bij het zeven van graankorrels worden bijvoorbeeld de graankorrels gesorteerd in twee groepen: graankorrels die wel door de zeef vallen en die niet door de zeef vallen. Ondertussen werden ze dus ook gemeten, op maat beoordeeld, als 'kleiner dan' de opening, of als 'groter of gelijk aan' de opening van de zeef. Het is ook een typische activiteit het kleuteronderwijs, om de kinderen te laten kennismaken met min of meer abstracte begrippen, dikwijls het criterium voor het sorteren, zoals grootte, vorm, kleur.