In-place algorithm
In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. An in-place algorithm updates its input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
- Comment
- enIn computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. An in-place algorithm updates its input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
- Has abstract
- enIn computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. An in-place algorithm updates its input sequence only through replacement or swapping of elements. 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 constant amount of extra space, counting everything including function calls and pointers. However, this form is very limited as simply having an index to a length n array requires 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 O(log n), though sometimes anything in 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 (DSPACE), counting pointer lengths. Therefore, the space requirements here have an extra log n factor compared to an analysis that ignores the length 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 reductions, it is more typical to always ignore output space (in these cases it is more essential that the output is write-only).
- Hypernym
- Algorithm
- Is primary topic of
- In-place algorithm
- Label
- enIn-place algorithm
- Link from a Wikipage to another Wikipage
- Algorithm
- Array data structure
- Bipartite graph
- BPL (complexity)
- Bubble sort
- Category:Algorithms
- Comb sort
- Computational complexity theory
- Computer science
- Connected component (graph theory)
- Data structure
- Depth-first search
- Deterministic space
- Divide and conquer algorithm
- Functional programming
- Heapsort
- Insertion sort
- L (complexity)
- Log-space reduction
- Memory management
- Miller–Rabin primality test
- Pointer (computer programming)
- Pollard's rho algorithm
- Purely functional data structure
- Quicksort
- Randomized algorithm
- Random walk
- Regular language
- RL (complexity)
- Selection algorithm
- Selection sort
- Shell sort
- Side effect (computer science)
- SL (complexity)
- Sorting algorithm
- Space complexity
- Subroutine
- Trim (programming)
- Undirected graph
- SameAs
- 4qLe2
- Algoritam za sortiranje u mestu
- Algoritmo in loco
- Algorytm in situ
- In-place algorithm
- In-Place-Algorithmus
- In-place algoritmus
- In-placeアルゴリズム
- m.01g41m
- På stedet-algoritme
- Q657037
- אלגוריתם תוך-מקומי
- الگوریتم درجا
- 原地算法
- 제자리 알고리즘
- Subject
- Category:Algorithms
- WasDerivedFrom
- In-place algorithm?oldid=1120616738&ns=0
- WikiPageLength
- 8596
- Wikipage page ID
- 219861
- Wikipage revision ID
- 1120616738
- WikiPageUsesTemplate
- Template:Code
- Template:Math
- Template:Redirect
- Template:Ref improve
- Template:Sup