Järjestettävyydestä

Järjestettävyydestä käytetään kuvaamaan kykyä asettaa esineet tai tiedot järjestykseen määritellyn suhteen mukaisesti. Keskeinen ajatus on, että kohteille voidaan määrittää binäärinen järjestysrelaatio, jonka avulla ne voidaan sijoittaa järjestykseen joko kokonaisessa tai osittaisessa muodossa.

Joukko S on järjestettävissä, jos sille voidaan määrittää järjestysrelaatio ≤, joka täyttää osittaisen järjestyksen vaatimukset. Osittaisjärjestyksessä (osittainen järjestys) suhde on refleksiivinen, antisymmetrinen ja transitiivinen, mutta ei välttämättä mahdollista kaikkien kohteiden välistä vertailua. Lineaarinen eli täydellinen järjestys on tapauksessa, jossa lisäksi kaikille erille a ja b pätee, että a ≤ b tai b ≤ a; tällöin kohteet voidaan asettaa kokonaisiin pareihin vertailtavaksi.

Esimerkkejä järjestettävyydestä ovat luonnollinen lukujärjestys (≤ on lineaarinen), aakkosellinen järjestys sanoille sekä aikajärjestys tapahtumien välillä. Näihin liittyy usein käytännön ilmentymiä, kuten lajittelua, hakua ja järjestettyjen tietojen ylläpitoa.

Järjestettävyys on keskeinen käsite sekä matematiikassa että informatiikassa. Matematiikassa sitä tarkastellaan osittais- ja lineaarijärjestysten kautta, sekä niiden tuottamien rakenteiden, kuten verkojen tai diagrammien, avulla. Informatikassa järjestettävyys mahdollistaa tehokkaan tietojen järjestämisen ja käsittelyn: lajittelu rakentuu toiminnaltaan vertailualustalle, ja monissa rakenteissa, kuten hakualgoritmeissa ja muistissa, järjestys on perusedselvitys.