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:
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)
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)
View all Courses