Generally, we can implement algorithms in-place and out-of-place.
However, I can't say for certain that radix sort can be implemented in both ways.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ What prevents you from checking that? $\endgroup$– user114966Commented Apr 15, 2021 at 0:35
-
$\begingroup$ @Dmitry well, it does not return a new array, but it does stores some variables. So I got my answer, 'it depends' (see Nathaniel's answer below) $\endgroup$– MontherCommented Apr 15, 2021 at 2:21
-
$\begingroup$ Analyzing a piece of Python code is out-of-scope for this site. Coding and implementation-specific questions are off-topic here. $\endgroup$– D.W. ♦Commented Apr 15, 2021 at 6:28
-
$\begingroup$ @D.W. See my edit. $\endgroup$– MontherCommented Apr 15, 2021 at 22:24
-
1$\begingroup$ You should check en.wikipedia.org/wiki/… $\endgroup$– NathanielCommented Apr 15, 2021 at 22:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It depends on the definition of in-place algorithm you are using.
- if in-place just means that the algorithm transforms the input without returning a new array, then yes;
- if you also want to use no additionnal data structure, or limit the additionnal space usage to be $o(n)$, then no, because of the creation of the arrays
countandoutput.
There are different meanings to an in-place algorithm, as stated here.
-
$\begingroup$ can we implement radix sorting algorithm without using additional space? $\endgroup$– MontherCommented Apr 15, 2021 at 2:07
-
2