Examples
Given an array a of n items, suppose we want an array that holds the same elements in reversed order and 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 a in appropriate order and then delete a.
Unfortunately, this requires O(n) extra space for having the arrays a and b available simultaneously. Also, allocation and deallocation are often slow operations. Since we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm which will only need constant additional storage for the auxiliary variables i and tmp, no matter how large the array is.
As another example, there are a number of sorting algorithms that can rearrange arrays into sorted order in-place, including: Bubble sort, Comb sort, Selection sort, Insertion sort, Heapsort, Shell sort.
Quicksort operates in-place on the data to be sorted as it only ever swaps two elements. However, most implementations require O(log n) space to keep track of the recursive function calls as part of the divide and conquer strategy; so Quicksort is not an in-place algorithm.
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.
Read more about this topic: In-place Algorithm
Famous quotes containing the word examples:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)