In-place Algorithm - Examples

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.

function reverse(a) allocate b for i from 0 to n b := a return b

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.

function reverse_in_place(a) for i from 0 to floor(n/2) tmp := a a := a a := tmp

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)

    “There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
    —Bernard Mandeville (1670–1733)

    “No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
    —André Breton (1896–1966)