listpartisjonering

Listpartisjonering, også kjent som liste­deling eller liste­partition, er en algoritmisk teknikk som deler en sekvens av elementer i to eller flere disjunkte undersekvenser basert på en eller flere kriterier. Metoden brukes i en rekke sammenhenger innen informatikk, spesielt i sorterings‑ og søkealgoritmer, datastrukturoptimalisering og distribusjon av data.

Den mest kjente anvendelsen er i partisjonssteget i quicksort, hvor en pivotelement velges og listen omorganiseres slik at alle elementer som er mindre enn pivoten kommer før den, mens større elementer plasseres etter. Resultatet er to sub‑lister som kan sorteres rekursivt. En lignende fremgangsmåte benyttes i algoritmer for median‑finning, som "selection"-algoritmen, samt i stabile sorteringsmetoder som merge‑sort når man slår sammen sorterte del‑lister.

Implementasjonen av listpartisjonering varierer etter datastruktur. For lineære tabeller (arrays) benyttes ofte to‑peker‑teknikker som Lomuto‑ og Hoare‑metodene, som opererer in‑place og krever O(1) ekstra plass. For lenkede lister kan man opprette to nye lister for elementer som er mindre eller større enn pivoten, eller justere pekere direkte i en enkelt passering. I begge tilfeller er tidskompleksiteten lineær, O(n), med n som antall elementer i den opprinnelige listen.

I databaseteori og distribuerte systemer refererer listpartisjonering til oppdeling av store datafiler eller tabeller i mindre partisjoner for å lette parallell behandling og lastenbalansering. Partitionering kan baseres på range‑ eller hash‑metoder, og er essensiell i systemer som Hadoop, Spark og tradisjonelle relasjonsdatabaser.

Relaterte konsepter inkluderer “stable partition”, som bevarer den relative rekkefølgen innenfor hver del, og “multi‑way partition”, som deler en liste i flere enn to segmenter i ett steg. Listpartisjonering er et grunnleggende verktøy i effektiv data‑manipulering og utgjør en viktig komponent i mange algoritmiske og system­messige løsninger.