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
Dynabee

... to incredibly high revs by following a circular wrist motion with the device. Modern devices come with electronic rev counters and light emitting diodes powered by ...

 
 
 
This page was created in 25.5 ms