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
Wheatley Heights, New York

... family size is 3.67. In the town the population is spread out with 30.3% under the age of 18, 8.1% from 18 to 24, 29.9% from 25 to 44, 23.8% from 45 to 64, and 7.9% who ...

 
 
 
This page was created in 25.7 ms