In-place algorithms

Sort algorithms usually have:

One input - an array of unsorted elements
One output - an array of the same elements sorted in order

There are other algorithms which work in a similar way. For example, a shuffle algorithm takes an array of elements which are in order, and mixes them up in a random order, just like shuffling a pack of cards. This algorithm is used in computer card games such as Solitaire.

Using two arrays

The natural way to write an algorithm like this would be to use 2 arrays, an input array containing the initial values, and an output array to hold the sorted values. The output array would start off empty (e.g. filled with zeros).

in = [9, 3, 6, 5, 2, 1, 8]
out = [0 , 0, 0, 0, 0, 0, 0]

After sorting, the output array would contain the elements in correct order:

in = [9, 3, 6, 5, 2, 1, 8]
out = [1, 2, 3, 5, 6, 8, 9]

In-place solutions

Using two arrays could be a problem is there is a very large amount of data, because it requires twice as much memory. We might prefer a version of the algorithm which works "in-place" - the calculation is performed by moving elements around in a single array. We start with:

in = [9, 3, 6, 5, 2, 1, 8]

And end up with this (with no second array required:

in = [1, 2, 3, 5, 6, 8, 9]

Many common search algorithms can be carried out in place.

In-place algorithms

Using two arrays

In-place solutions

Sort algorithms

See also

Links