Ongesorteerd

Ongesorteerd is een aanduiding voor een verzameling of lijst waarvan de elementen geen specifieke volgorde volgen. De volgorde kan willekeurig of afhankelijk van de input zijn, maar er is geen sleutel- of ordecriterium dat consistent geldt over alle elementen. In tegenstelling tot gesorteerde collecties, waar elementen zijn geplaatst volgens een overeenkomstige sleutel (bijv. numeriek oplopend of alfabetisch), geeft ongesorteerd aan dat zo'n ordening ontbreekt of niet behouden wordt.

In informatica komt een ongesorteerde lijst vaak voor bij ruwe data, gebruikersinvoer of resultaten van bewerkingen die geen sortering afdwingen. Zo kan zoeken in een ongesorteerde lijst duurder zijn: lineair zoeken bezoekt mogelijk alle elementen, met tijdscomplexiteit O(n), terwijl in een gesorteerde lijst vaak sneller gezocht kan worden met binaire zoekopdrachten (O(log n)).

Het sorteren van een ongesorteerde collectie zet deze om in een gesorteerde structuur. Sorteralgoritmen zoals quicksort, mergesort en heapsort kennen verschillende tijdcomplexiteiten; gemiddeld wordt vaak O(n log n) bereikt, terwijl sommige algoritmen in slechtste gevallen O(n^2) kunnen vereisen, afhankelijk van het algoritme en de aard van de invoer.

In praktische toepassingen kan ongesorteerd ook betekenen dat volgorde niet relevant is voor bepaalde bewerkingen, zoals controle op uniciteit, deduplicatie of groepering. Sommige data kunnen bovendien gedeeltelijk gesorteerd zijn of op insertion order benaderd, maar dat maakt ze nog niet volledig gesorteerd.

Zie ook: sorteren, sorteeralgoritmen, lineair zoeken, binaire zoekopdracht.