I was thinking of radix sort, and at a sudden thought that it uses de facto the paradigm of dynamic programming, but I soon changed my mind to greedy algorithm. Is it really a greedy algorithm?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What heuristic do you see here? $\endgroup$– Karolis JuodelėDec 11, 2013 at 19:56
-
$\begingroup$ Basically, I find radix to be greedy because: let's suppose we are looking for only the minimum element (first in ascending order) and later the second minimum, and so forth... for deciding these we are going for the local minimum( the i. digit of the particular number) and using that we get the global optimum $\endgroup$– genDec 11, 2013 at 20:26
-
3$\begingroup$ There are formal models for greedy algorithms (priority algorithms) and dynamic programming (BT, pBT) and so on, and radix sort probably doesn't fit any of them. $\endgroup$– Yuval FilmusDec 11, 2013 at 21:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Personally, I would not call it a greedy algorithm. I'm not sure that's a useful way to think about it.
A greedy algorithm optimizes some global objective function by making small choices, where at each step we make a locally optimal choice (among all the choices at each step, we choose the one that best improves our objective function). In a greedy algorithm, the objective function monotonically increases at each step of the algorithm. I don't see any sense in which radix sort has this form.
This becomes clearest if we look at the version of radix sort that starts by sorting on the least significant digit, then the next-least significant digit, etc. Here the objective function does not monotonically increase. The first step can take you further away from being sorted, but then later steps bring you back.
For instance, consider the list $[0101, 0010, 0001]$. Let's look at what happens if we apply radix sort to this list. The first pass will transform this to $[0010, 0101, 0001]$: it got further away from being sorted. After the second pass, we get $[0101, 0001, 0010]$, then after the third pass we get $[0001, 0010, 0101]$: it is finally sorted. So, we started out being close to sorted, then we got farther away from being sorted, then we got closer -- not exactly the characteristic of a greedy algorithm.
For an even better example, consider the list $[0001, 0010, 0101]$. Let's look at what happens if we apply radix sort to this list, even though it happens to already be sorted. The first pass will transform this to $[0010, 0001, 0101]$. I don't care what your global objective function is; this has certainly made the global objective function worse, because it changed the list from being completely-sorted to being not-sorted. So, this shows that radix sort doesn't seem to be a greedy algorithm (at least if you start by sorting on the least significant bit).
There's an alternative version of radix sort where we sort first by sorting on the most significant digit, then the next-most significant digit, etc. This does feel closer to a greedy algorithm, though I'm not sure that viewpoint is really useful in any practical way.
It is definitely not a dynamic programming algorithm.
I'm not sure that trying to classify it in this way is useful or helpful. I don't think it'll help you, e.g., understand how greedy algorithms work, or help you design better greedy algorithms in the future in other settings. I'd suggest you think about radix sort on its own terms: it just is what it is.
-
$\begingroup$ thanks for the detailed answer. as for your last paragraph: i don't think that it makes much sense to classify either, i was just wondering $\endgroup$– genDec 12, 2013 at 16:29