Dutch flag is like a radix sort in that we know the range of values, and the range is fixed and small compared to the size of the array. All we don't know is how many of each of the three values occur in the array. Dutch Flag is not a comparison based algorithm because you can write it without ever comparing one element in the array to another (ie < or >). Don
On Jan 23, 10:49 pm, atul anand <[email protected]> wrote: > @Don : if i am not wrong ... American flag problem is closely related to > radix sort not dutch flag. > > > > On Mon, Jan 23, 2012 at 11:16 PM, Don <[email protected]> wrote: > > The Dutch Flag problem falls into the same category as radix sort, > > which is not a comparison-based sorting algorithm. > > Don > > > On Jan 23, 1:26 am, atul anand <[email protected]> wrote: > > > Hi all, > > > > 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 > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
