# Difference between revisions of "Talk:TADM2E 4.4"

From Algorithm Wiki

(Created page with "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 w...") |
|||

(One intermediate revision by one other user not shown) | |||

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). | ||

+ | |||

+ | |||

+ | |||

+ | 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. |

## Latest 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.