Algorithms in Computer Science are classified into various categories depending on diverse characteristics of the algorithms and also on the resource usage of them.
In-place and out-of-place are one of such categorization depending on the extra memory space used by an algorithm to solve a problem.
Let us consider each one separately.
In-place algorithms
- In-place algorithms convert the input in to an output without allocating extra memory space for the process of problem solving. It uses the available space given as the input and replaces input with output.
- An in-place algorithm can use some small amount of non-constant additional memory.
- The additional space of O (log n) is the accepted limit but sometimes lower than O(n) is also approved.
- Bubble sort and Selection sort are two in-place algorithms in the context.
Out-of-place algorithms
- An out-of-place algorithm is the opposite of in-place and needs growing amount of memory (usually O(n) or bigger than that) to process the input into output.
- The standard merge sort algorithm is an example of out-of-place algorithm as it requires O(n) extra space for merging.
When studying algorithms in Computer Science, we come across algorithms that fall into these two categories. Choosing what algorithm among them to be the best is subjective, yet it is good to know the following before you make that decision.
Working in-place is a good way to save time and space. An in-place algorithm avoids the cost of initializing or copying data structures.
But, an in-place algorithm can cause side effects. The input is usually destroyed to replace with output which can affect code outside of the method.
Therefore, generally out-of-place algorithms are considered safer because they avoid such side effects.
One should only use an in-place algorithm if the space is constrained or the original input is not useful anymore (even for debugging).
Thanks for reading! Let me know if this was helpful. See you with another post :)
Comments
Post a Comment