Regarding complexity (if a comparison-based sorting algorithm is used)

Question

since we all know that any sorting algorithm based on a comparison model has a lower bound nlogn ie Omega (nlogn). what mathematically can be proved.

but, as we all know, the Dutch flag problem can sort 3 separate elements (which are reused) in O (n) time. It is also based on a comparison model, but it can sort in O (n) time. since we can justify the lower bound of sorting based on the comparison model, because the Dutch flag problem may violate this.

please help me understand the difference .....

thanks

Answer 1

In my opinion, this is not a corresponding “contradiction” of the lower boundary, since this is a special case (the possible range of values ​​is less than the total number of elements, in fact it is constant 3) which can be used to search for an algorithm faster than O (N * logN), which is the lower bound for the general sorting algorithm based on comparison (i.e. where you have no information about the contents of the sequence).

Usually, when N elements are in the range 0..K with K <N, you can use sorting without comparison efficiently, for example sorting sorting, to solve the problem in O (N).

Answer 2

The Omega(n log n) score Omega(n log n) provides a lower bound for sorting arbitrary elements based on comparison.

What the Dutch flag is considering is the case when you do not have arbitrary elements, but only three options for each element.

Thus, the Omega(n log n) estimate is performed for the task as a whole without additional restrictions. However, if you impose other restrictions (for example, there are only three options for each element), you can find algorithms better than this estimate, simply because then you consider a specific case where you can apply other heuristics, etc.

Answer 3

The fact is that the set of Dutch flags is not completely streamlined. There are many equal elements, because when you count individual objects, this is a set (no more) of size 3.

The Omega(n log n) constraint is probably only complicated if either a<b or b>a holds for objects a and b (aka: all objects are different )

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

Assuming there are at least two different objects, I believe that the correct border is something like Omega(n log m) , where n is the number of objects and m is the number of separate objects (which do not sort the same), Simply put , log m is the number of solutions needed to find the output bucket. In the general case, O(log m)=O(log n) if the number of equal objects is small. In the Dutch flag problem m=3 .

Radix sort uses this differently. It is also considered linear. However, this requires log m , and m is the number of possibly individual elements. So actually Radix sorting is also Omega(n log m) , where m is the number of objects that it can distinguish.

Answer 4

The Dutch flag problem has some more basic data than regular sorting, it knows that there are three different values, and if you look at the wikipedia page for the algorithm:

 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 does not use comparison between pairs of elements, it just used comparison between the lower / middle / upper border and elements, which is not related to other comparison methods that were used in normal sorting, you can compare it with Counting Sort.

Answer 5

The problem with the Dutch flag is rather a splitting algorithm.

This is just the first step to sorting. You can use it for sorting (applying it to partitions again and again), but I think you end up being omega (nlogn).

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