Encyclopedia > Work-in-place

  Article Content

Work-in-place

In computer science, algorithms work-in-place if they transform a data structure without requring extra memory (or disk) space. The input is overwritten with the output.

For example, sorting algorithms that can rearrange arrays into a desired order in-place include:

In computational complexity theory, in-place algorithms have O(1) space complexity.

Functional programming languages often discourage or don't support in-place algorithms that overwrite data (rather than merely constructing new data). This is a type of side effect. Note that it is possible in principle to carefully construct in-place algorithms that don't modify data (unless the data is no longer being used), but this is rarely done in practice. See purely functional data structures[?].



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Brazil

... was once Portuguese, subsequent waves of immigration have contributed to a diverse ethnic and cultural heritage. Brazil is the only Portuguese-speaking nation in th ...

 
 
 
This page was created in 26.9 ms