Difference between revisions of "Talk:TADM2E 4.4"

From Algorithm Wiki
Jump to: navigation, search
m
Line 5: Line 5:
  
 
Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).
 
Each pass is O(n) since we have to visit each element, so the entire algorithm is O(n).
 +
  
  
Line 17: Line 18:
 
         if a[index].color=="blue"
 
         if a[index].color=="blue"
 
             swap(a,++index_blue,index)
 
             swap(a,++index_blue,index)
 +
 +
The  ''swap''' above makes it a non-stable sort.

Revision as of 07:31, 30 December 2016

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

   index_red=-1
   for index =0 to a.length-1
      if a[index].color == "Red"
         swap(a,++index_red,index)
   index_blue=index_red
   for index = index_blue+1 to a.length-1
       if a[index].color=="blue"
            swap(a,++index_blue,index)

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