In-place algorithm
Encyclopedia
In computer science
, an in-place algorithm (or in Latin
in situ) is an algorithm
which transforms input using a data structure
with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
An algorithm is sometimes informally called in-place as long as it overwrites its input with its output. In reality this is not sufficient (as the case of quicksort demonstrates) nor is it necessary; the output space may be constant, or may not even be counted, for example if the output is to a stream. On the other hand, sometimes it may be more practical to count the output space in determining whether an algorithm is in-place, such as in the first reverse example below; this makes it difficult to strictly define in-place algorithms. In theory applications such as log-space reduction
s, it's more typical to always ignore output space (in these cases it's more essential that the output is write-only).
function reverse(a[0..n])
allocate b[0..n]
for i from 0 to n
b[n - i] = a[i]
return b
Unfortunately, this requires O(n) extra space to create the array b, and allocation is often a slow operation. If we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm:
function reverse-in-place(a[0..n])
for i from 0 to floor(n/2)
swap(a[i], a[n-i])
As another example, there are a number of sorting algorithm
s that can rearrange arrays into sorted order in-place, including: Bubble sort
, Comb sort
, Selection sort
, Insertion sort
, Heapsort
, Shell sort
.
Quicksort is commonly described as an in-place algorithm, but is not in fact one. Most implementations require O(log n) space to support its divide and conquer
recursion.
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
and reverse may be done in-place.
, in-place algorithms include all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular language
s. In fact, it does not even include any of the examples listed above.
For this reason, we also consider algorithms in L
, the class of problems requiring O(log n) additional space, to be in-place. Although this seems to contradict our earlier definition, we have to consider that in the abstract world our input can be arbitrarily large. On a real computer, a pointer requires only a small fixed amount of space, because the amount of physical memory is limited, but in general O(log n) bits are required to specify an index into a list of size n.
Does this mean quicksort is in-place after all? Not at all—technically, it requires O(log2 n) space, since each of its O(log n) stack frames contains a constant number of pointers (each of size O(log n)).
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, a problem that requires 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
or testing whether two graphs have the same number of connected component
s. See SL (complexity)/SL for more information.
. For example, say we wish to know if two vertices in a graph of n vertices are in the same connected component
of the graph. There is no known simple, deterministic, in-place algorithm to determine this, but if we simply start at one vertex and perform a random walk
of about 20n3 steps, the chance that we will stumble across the other vertex provided that it's 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
. See RL and BPL
for more discussion of this phenomenon.
languages often discourage or don't support explicit in-place algorithms that overwrite data, since this is a type of 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 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 don't modify data (unless the data is no longer being used), but this is rarely done in practice. See purely functional data structures.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, an in-place algorithm (or in Latin
Latin
Latin is an Italic language originally spoken in Latium and Ancient Rome. It, along with most European languages, is a descendant of the ancient Proto-Indo-European language. Although it is considered a dead language, a number of scholars and members of the Christian clergy speak it fluently, and...
in situ) is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
which transforms input using a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
An algorithm is sometimes informally called in-place as long as it overwrites its input with its output. In reality this is not sufficient (as the case of quicksort demonstrates) nor is it necessary; the output space may be constant, or may not even be counted, for example if the output is to a stream. On the other hand, sometimes it may be more practical to count the output space in determining whether an algorithm is in-place, such as in the first reverse example below; this makes it difficult to strictly define in-place algorithms. In theory applications such as log-space reduction
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers...
s, it's more typical to always ignore output space (in these cases it's more essential that the output is write-only).
Examples
Suppose we want to reverse an array of n items. One simple way to do this is:function reverse(a[0..n])
allocate b[0..n]
for i from 0 to n
b[n - i] = a[i]
return b
Unfortunately, this requires O(n) extra space to create the array b, and allocation is often a slow operation. If we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm:
function reverse-in-place(a[0..n])
for i from 0 to floor(n/2)
swap(a[i], a[n-i])
As another example, there are a number of sorting algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
s that can rearrange arrays into sorted order in-place, including: Bubble sort
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
, Comb sort
Comb sort
Comb sort is a relatively simplistic sorting algorithm originally designed by Włodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine . Comb sort improves on bubble sort, and rivals algorithms like Quicksort...
, Selection sort
Selection sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort...
, Insertion sort
Insertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
, Heapsort
Heapsort
Heapsort is a comparison-based sorting algorithm to create a sorted array , and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O runtime...
, Shell sort
Shell sort
Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart. Its first version was published by Donald Shell in 1959. The running...
.
Quicksort is commonly described as an in-place algorithm, but is not in fact one. Most implementations require O(log n) space to support its divide and conquer
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
recursion.
Most selection algorithm
Selection algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list . This includes the cases of finding the minimum, maximum, and median elements. There are O, worst-case linear time, selection algorithms...
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
Trim (programming)
In programming, trim or strip is a common string manipulation function which removes leading and trailing whitespace from a string.For example, the text' this is a test 'would be changed, after trimming, to'this is a test'-Variants:...
and reverse may be done in-place.
In computational complexity
In computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, in-place algorithms include all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular language
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
s. In fact, it does not even include any of the examples listed above.
For this reason, we also consider algorithms in L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
, the class of problems requiring O(log n) additional space, to be in-place. Although this seems to contradict our earlier definition, we have to consider that in the abstract world our input can be arbitrarily large. On a real computer, a pointer requires only a small fixed amount of space, because the amount of physical memory is limited, but in general O(log n) bits are required to specify an index into a list of size n.
Does this mean quicksort is in-place after all? Not at all—technically, it requires O(log2 n) space, since each of its O(log n) stack frames contains a constant number of pointers (each of size O(log n)).
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, a problem that requires O(n) extra space using typical algorithms such as depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
(a visited bit for each node). This in turn yields in-place algorithms for problems such as determining if a graph is bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
or testing whether two graphs have the same number of connected component
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
s. See SL (complexity)/SL for more information.
Role of randomness
In many cases, the space requirements for an algorithm can be drastically cut by using a randomized algorithmRandomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
. For example, say we wish to know if two vertices in a graph of n vertices are in the same connected component
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
of the graph. There is no known simple, deterministic, in-place algorithm to determine this, but if we simply start at one vertex and perform a random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
of about 20n3 steps, the chance that we will stumble across the other vertex provided that it's 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
Miller-Rabin primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithmwhich determines whether a given number is prime,...
, and there are also simple in-place randomized factoring algorithms such as Pollard's rho algorithm
Pollard's rho algorithm
Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.-Core ideas:...
. See RL and BPL
BPL (complexity)
In computational complexity theory, BPL , sometimes called BPLP , is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error...
for more discussion of this phenomenon.
In functional programming
Functional programmingFunctional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
languages often discourage or don't support explicit in-place algorithms that overwrite data, since this is a type of side effect
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
; 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 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 don't modify data (unless the data is no longer being used), but this is rarely done in practice. See purely functional data structures.
See also
- Table of in-place and not-in-place algorithms