Talk:TADM2E 4.4

From Algorithm Wiki
Revision as of 07:31, 30 December 2016 by Joky (Talk | contribs)

Jump to: navigation, search

Why break up the pairs and use buckets? It seems like you simply need three passes: First pass - get the reds and insert them in order into a new array of size n (assuming we can use additional space) Second pass - get the blues and insert them in order into the array Third pass - get the yellows and insert them in order into the array

Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).

EDIT: Why three passes ? .Two passes can do it

   for index =0 to a.length-1
      if a[index].color == "Red"
   for index = index_blue+1 to a.length-1
       if a[index].color=="blue"

The swap' above makes it a non-stable sort.