Editing In-place algorithm

{{Short description|Type of computer science algorithm}}
{{Redirect|In-place|execute in place file systems|Execute in place}}

{{ref improve|date=January 2015}}
In [[computer science]], an '''in-place algorithm''' is an [[algorithm]] that operates directly on the input [[data structure]] without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called '''not-in-place''' or '''out-of-place'''.

In-place can have slightly different meanings. In its strictest form, the algorithm can only have a [[Space complexity|constant amount of extra space]], counting everything including [[Subroutine|function]] calls and [[Pointer (computer programming)|pointers]]. However, this form is very limited as simply having an index to a length {{math|''n''}} array requires {{math|''O''(log ''n'')}} bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is {{math|''O''(log ''n'')}}, though sometimes anything in {{math|''o''(''n'')}} is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity ([[Deterministic space|DSPACE]]), counting pointer lengths. Therefore, the space requirements here have an extra {{math|log ''n''}} factor compared to an analysis that ignores the lengths of indices and pointers.  

An algorithm may or may not count the output as part of its space usage. Since in-place algorithms usually overwrite their input with output, no additional space is needed. When writing the output to write-only memory or a stream, it may be more appropriate to only consider the working space of the algorithm. In theoretical applications such as [[log-space reduction]]s, it is more typical to always ignore output space (in these cases it is more essential that the output is ''write-only'').

== Examples ==

Given an [[Array data structure|array]] {{code|a}} of {{math|''n''}} items, suppose we want an array that holds the same elements in reversed order and to dispose of the original. One seemingly simple way to do this is to create a new array of equal size, fill it with copies from {{code|a}} in the appropriate order and then delete {{code|a}}.

  '''function''' reverse(a[0..n - 1])
      allocate b[0..n - 1]
      '''for''' i '''from''' 0 '''to''' n - 1
          b[n − 1 − i] := a[i]
      '''return''' b

Unfortunately, this requires {{math|''O''(''n'')}} extra space for having the arrays {{code|a}} and {{code|b}} available simultaneously. Also, [[Manual memory management|allocation]] and deallocation are often slow operations. Since we no longer need {{code|a}}, we can instead overwrite it with its own reversal using this in-place algorithm which will only need constant number (2) of integers for the auxiliary variables {{code|i}} and {{code|tmp}}, no matter how large the array is.

  '''function''' reverse_in_place(a[0..n-1])
      '''for''' i '''from''' 0 '''to''' floor((n-2)/2)
          tmp := a[i]
          a[i] := a[n − 1 − i]
          a[n − 1 − i] := tmp

As another example, many [[sorting algorithm]]s rearrange arrays into sorted order in-place, including: [[bubble sort]], [[comb sort]], [[selection sort]], [[insertion sort]], [[heapsort]], and [[Shell sort]]. These algorithms require only a few pointers, so their space complexity is {{math|''O''(log ''n'')}}.<ref>The bit space requirement of a pointer is {{math|''O''(log ''n'')}}, but pointer size can be considered a constant in most sorting applications.</ref>

[[Quicksort]] operates in-place on the data to be sorted. However, quicksort requires {{math|''O''(log ''n'')}} stack space pointers to keep track of the subarrays in its [[divide and conquer algorithm|divide and conquer]] strategy. Consequently, quicksort needs {{math|''O''(log{{sup|2}} ''n'')}} additional space. Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only {{math|''O''(log ''n'')}} additional pointers are usually considered in-place algorithms.

Most [[selection algorithm]]s are also in-place, although some considerably rearrange the input array in the process of finding the final, constant-sized result.

Some text manipulation algorithms such as [[Trim (programming)|trim]] and reverse may be done in-place.

== In computational complexity ==
{{See also|SL (complexity)}}
In [[computational complexity theory]], the strict definition of in-place algorithms includes all algorithms with {{math|''O''(1)}} space complexity, the class '''[[Deterministic space|DSPACE]]'''(1). This class is very limited; it equals the [[regular language]]s.<ref>Maciej Liśkiewicz and Rüdiger Reischuk. [http://citeseer.ist.psu.edu/34203.html The Complexity World below Logarithmic Space]. ''Structure in Complexity Theory Conference'', pp. 64–78. 1994. Online: p. 3, Theorem 2.</ref> In fact, it does not even include any of the examples listed above.

Algorithms are usually considered in [[L (complexity)|L]], the class of problems requiring {{math|''O''(log ''n'')}} additional space, to be in-place. This class is more in line with the practical definition, as it allows numbers of size {{math|''n''}} as pointers or indices. This expanded definition still excludes quicksort, however, because of its recursive calls.  

Identifying the in-place algorithms with L has some interesting implications; for example, it means that there is a (rather complex) in-place algorithm to determine whether a path exists between two nodes in an [[undirected graph]],<ref>{{citation
 | last = Reingold | first = Omer | author-link = Omer Reingold
 | doi = 10.1145/1391289.1391291
 | issue = 4
 | id = {{ECCC|2004|04|094}}
 | journal = [[Journal of the ACM]]
 | mr = 2445014
 | pages = 1–24
 | title = Undirected connectivity in log-space
 | volume = 55
 | year = 2008| s2cid = 207168478 }}</ref> a problem that requires {{math|''O''(''n'')}} extra space using typical algorithms such as [[depth-first search]] (a visited bit for each node). This in turn yields in-place algorithms for problems such as determining if a graph is [[bipartite graph|bipartite]] or testing whether two graphs have the same number of [[connected component (graph theory)|connected component]]s.

== Role of randomness ==
{{See also|RL (complexity)|BPL (complexity)}}
In many cases, the space requirements of an algorithm can be drastically cut by using a [[randomized algorithm]]. For example, if one wishes to know if two vertices in a graph of {{math|''n''}} vertices are in the same [[Connected component (graph theory)|connected component]] of the graph, there is no known simple, deterministic, in-place algorithm to determine this. However, if we simply start at one vertex and perform a [[random walk]] of about {{math|20''n''{{sup|3}}}} steps, the chance that we will stumble across the other vertex provided that it is in the same component is very high. Similarly, there are simple randomized in-place algorithms for primality testing such as the [[Miller–Rabin primality test]], and there are also simple in-place randomized factoring algorithms such as [[Pollard's rho algorithm]].

== In functional programming ==
{{See also|Purely functional data structure}}
[[Functional programming]] languages often discourage or do not support explicit in-place algorithms that overwrite data, since this is a type of [[side effect (computer science)|side effect]]; instead, they only allow new data to be constructed. However, good functional language compilers will often recognize when an object very similar to an existing one is created and then the old one is thrown away, and will optimize this into a simple mutation "under the hood".

Note that it is possible in principle to carefully construct in-place algorithms that do not modify data (unless the data is no longer being used), but this is rarely done in practice. 

== See also ==
* [[Sorting algorithm#Comparison of algorithms|Table of in-place and not-in-place sorting algorithms]]

== References ==
<references/>

{{DEFAULTSORT:In-Place Algorithm}}
[[Category:Algorithms]]