In-place algoritme

En algoritme fungerer på stedet eller in situ hvis den bortsett fra lagring av de nødvendige dataene som skal behandles minne bare en konstant, som kreves av den uavhengige dataen for å bli behandlet mengde minne. Algoritmen overskriver inngangsdata med utdata.

For eksempel fungerer Bubblesort- algoritmen på plass, mens Bucketsort fungerer ut av sted , fordi utdataene må lagres i en annen liste, som imidlertid ikke påvirker de originale dataene. Den plassen kompleksiteten av sted i arbeidende algoritmer, i Landau notasjon uttrykt .

Oppgaver kan ikke utføres direkte på rent funksjonelle programmeringsspråk, og det er derfor ikke lett å beskrive stedlige algoritmer der. Imidlertid, ved å optimalisere kompilatoren, blir ikke-sted-algoritmer automatisk oversatt til ekvivalente sted-algoritmer på noen funksjonelle programmeringsspråk. For eksempel erkjenner Glasgow Haskell Compiler at etter at en modifisert kopi av en variabel er opprettet, brukes ikke originalen lenger. I dette tilfellet implementeres kopien internt som en oppgave, og derfor brukes ikke noe ekstra minne.