Sorteren

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search

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

Het kan gaan om fysieke objecten die worden ingedeeld in groepen die bij elkaar geplaatst worden (alleen maar dicht bij elkaar, of in stapels, zakjes/zakken, vakken, kastplanken, enz.), of om data (die al of niet betrekking hebben op fysieke objecten). Bij data (gegevens) helpt de computer bij het sorteren door het toepassen van een sorteeralgoritme. De data kunnen bijvoorbeeld geplaatst zijn in een spreadsheet, een regel per item, waarbij de waarden van de sorteersleutel in een kolom staan. Ook kan de sorteervolgorde gebaseerd zijn op meerdere kolommen. Bij spreadsheets is zo'n sorteeralgoritme ingebouwd.

Als het aantal van toepassing zijnde waarden van de sorteersleutel klein is, is het (behalve bij zware fysieke objecten) maar een kleine stap van indelen in groepen van gelijke waarde 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 gewoon gebruikt worden voor het indelen in groepen.

Bij het sorteren van bijvoorbeeld de getallen 2, 1, 2, 3 in oplopende volgorde krijgt men het unieke resultaat 1, 2, 2, 3. Een rij van vier fysieke objecten waarvan er twee identiek zijn, kan men op basis van een totale ordening van de drie soorten in principe in twee volgordes sorteren, die onderscheidbaar zijn op basis van het sorteerproces (de twee identieke worden al of niet onderling verwisseld), 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 fysieke objecten waarvan sommige identiek zijn kan men dan nog twee versies van stabiliteit onderscheiden; in de strikte versie blijven ook identieke objecten in dezelfde onderlinge volgorde staan.

Gesorteerd kunnen bijvoorbeeld worden ideeën, getallen, eigenschappen (bv. kleur), dieren, planten, woorden of gevoelens zijn. Ook het criterium kan zeer gevarieerd zijn, bijvoorbeeld sorteren volgens grootte, ouderdom, dikte, hardheid, licht-gevoeligheid, politieke overtuiging, herkomst, inkomen, intelligentie, smeltpunt, of haarkleur.

Sorteren wordt vaak voorafgegaan door een vorm van meten en classificeren. Ook kan dit gelijk 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 verwaarloosbaar is 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 data 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 de lemma's. 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 binair zoeken, 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 binair kan zoeken. Als de waarden van de sorteersleutel deel uit maken van de gepresenteerde data kan men ook bij het bekijken van fragmenten van de lijst op elk moment gemakkelijk aan de data zien (eraan herinnerd worden) 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.