Given an
array of 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 in the appropriate order and then delete .
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 extra space for having the arrays and available simultaneously. Also,
allocation and deallocation are often slow operations. Since we no longer need , 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 and , 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 algorithms 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 .
Quicksort operates in-place on the data to be sorted. However, quicksort requires stack space pointers to keep track of the subarrays in its
divide and conquer strategy. Consequently, quicksort needs additional space. Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only additional pointers are usually considered in-place algorithms. Most
selection algorithms 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 computational complexity ==