Regarding complexity (if comparison based sorting algorithm used)

Question

as we all know that any sorting algorithm based on comparison model has lower bound of nlogn i.e Omega(nlogn). which can be proved mathematically.

but as we all know dutch flag problem can sort 3 distinct elements (used repeatedly) in O(n) time.It is also based on comparison model but can sort in O(n) time. so how can we justify lower bound of sorting based on comparison model , because dutch flag problem kinda violates that.

please help me understanding the difference.....

Thanks

Answer 1

In my opinion, this is not a relevant "contradiction" of the lower bound, because it is a particular case (the possible range of values is smaller than the total number of elements, in fact it is a constant, 3) which can be exploited to find an algorithm faster than O(N*logN), which is the lower bound for a general comparison-based sorting algorithm (i.e. where you have no information about the content of the sequence).

Generally in the case where N elements are in the range 0..K with K < N you can efficiently exploit a non-comparison sort like counting sort to solve the problem in O(N).

Answer 2

The bound Omega(n log n) gives a lower bound for comparison-based sorting of arbitrary elements.

What the dutch flag problem considers is just a case where you do not have arbitrary elements, but just three options for each element.

Thus, the bound Omega(n log n) holds for the problem in general, without additional constraints. However, if you impose other constraints (for example, that there are just three options for each element), you might well be able to find algorithms better than this bound simply because you then consider a particular case where you might be able to apply other heuristics, etc.

Answer 3

Dutch flag problem has some more basic data than normal sort, it knows there is three different value and if you look at wikipedia page for algorithm it's:

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

In fact it doesn't used comparison between pair of elements, it just used comparison between lower/medium/upper bound and elements, which is irrelevant to other comparison methods which used in normal sorting, you can compare it with Counting Sort.

Answer 4

The point is: the dutch flag set is not totally ordered. There are many equal elements, in fact when you count distinct objects, it is a set of (at most) size 3.

The Omega(n log n) bound is probably only hard when for objects a and b either a<b or b>a holds (aka: all objects are distinct)

In fact, I can sort in O(0), when all objects must be null.

Assuming that there are at least two distinct objects, I believe the proper bound is something like Omega(n log m) where n is the number of objects and m is the number of distinct objects (that do not sort equal). Simply speaking, log m is the number of decisions needed to find the output bucket. In the general case, O(log m)=O(log n), if the amount of equal objects is low. In the dutch flag problem, m=3.

Radix sort exploits this in a different way. It is also considered to be linear. However, it requires log m passes over the data, where m is the number of possibly distinct elements. So actually, Radix sort also is Omega(n log m), where m is the number of objects it can discern.

Answer 5

Dutch Flag problem is more of a partitioning algorithm.

It's only a first step to sorting. You could use it for sorting (by applying it to the partitions over and over again), but i guess you end up with Omega(nlogn).

Knowing the number of different values (3 in case of the flag) and their values (blue, white, red) is a very rare case.