What is inplace algorithm in data structures and algorithms
Inplace algorithm
There are devices that don’t have enough
memory space. For example, mobile phones, PDA, etc. For these devices, the
problem is more time is spent on I/O (input/output) operation than calculation.
Inplace algorithm  an algorithm that
uses a small constant amount of extra space in addition to the original input,
usually overwrite the input space.
Example:
Reverse the string “WELCOME”.
Method
1:
Assume that the letters are stored in an
array A1 as follows;
W

E

L

C

O

M

E

To reverse the string ‘WELCOME’, we can
create another array A2 and read A1 in reverse and paste each element in A2
from the beginning as follows;
Noninplace algorithm uses O(n) extra space 
Drawback:
This method needs O(n) additional memory
space. That is, we create another array of same size and paste the characters
from the given string.
Method
2:
Assume that the letters are stored in an
array A1 as follows;
W

E

L

C

O

M

E

To reverse the string ‘WELCOME’, we can exchange
the element stored in the first index with the last, second index with the last
but one, and so on until entire string is reversed. You can observe it from the
figure below;
Inplace algorithm  uses O(1) extra space to swap 
Advantage:
This method implements inplace algorithm to reverse the given
string. O(1) constant extra space is used to reverse the string. [This
one character space is used to swap two characters from the string. Temp =
A1[0], A1[0] = A1[6], A1[6] = temp]
Example
inplace algorithms:
 Insertion sort
 Selection sort
Example
of notinplace (outofplace) algorithms:
 Merge sort
******************
inplace sorting algorithm
examples for inplace algorithm
how does inplace algorithm works
how does inplace algorithm save space
how much extra space an inplace algorithm need
No comments:
Post a Comment