In-place Algorithm in 5 minutes
Let’s look at what is the in-place algorithm with some examples
Table of Content:
- What is the in-place algorithm(with example)?
- Make your hands dirty
What is the in-place algorithm(with example)?
In computer science, an in-place algorithm is an algorithm that transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. — From Wikipedia
The Wikipedia explanation is not straightforward. Let’s take reversing a list as an example:
Reverse a list(In-place):
Reverse a list(Non-in-place):
As you can see in this Reverse a list example. The in-place solution only needs O(1) extra memory while the not-in-place need O(n) extra memory.
Make your hands dirty:
You cannot understand one concept until you make your hands dirty. I have prepared some exercises for you to practice with, remember to solve the following questions in-place:
For more exercises, you can look at the following page:
For short, an in-place algorithm means transforming the original input using only constant extra memory. Strictly, an in-place needs only O(1) memory beyond the items being sorted; sometimes O(log(n)) additional memory is considered “in-place”.