Related Tags

algorithm
space complexity

# What are in-place and out-of-place algorithms?

In-place algorithms are a type of algorithm in computer science that do not require additional space for their operation. Additional variables that consume a small amount of nonconstant memory are acceptable. This extra space should be less than $O(log\space n)$, however, below $O(n)$ is sometimes allowed. The opposite of an in-place algorithm is an out-of-place or not-in-place algorithm.

Updating operations in in-place algorithms usually involve overwriting previous data. Let’s consider two approaches to reversing a list:

1. out-of-place
2. in-place

## Out-of-place

For an out-of-place algorithm, the simplest solution may be to traverse the original list in reverse and construct another list using that data. Once the list is fully traversed, the new list is constructed.

array = ['a', 'b', 'c', 'd']
new_array = ['a'] * len(array)

print("Before",array)

lenght = len(array) - 1

for i in range(lenght):
new_array[i] = array[lenght - i]

array = new_array
print("After",array)

1 of 7

## In-place

In an in-place algorithm, we will swap the first element of the list with the last element​, and so on, until we’ve completed the operation.

array = ['a', 'b', 'c', 'd']

print("Before",array)

lenght = len(array) - 1

for i in range(lenght // 2 + 1):
#print("Swapping", array[i], 'and', array[lenght - i])

tmp = array[i]
array[i] = array[lenght - i]
array[lenght - i] = tmp

print("After",array)

1 of 4

RELATED TAGS

algorithm
space complexity