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 , however, below 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:
- out-of-place
- 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) - 1for i in range(lenght):new_array[i] = array[lenght - i]array = new_arrayprint("After",array)
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) - 1for 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] = tmpprint("After",array)
