If you want to make money online : Register now

[Solved]: Is radix sort a greedy algorithm?

, , No Comments
Problem Detail: 

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?

Asked By : gen

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18889

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback