Difference between revisions of "Talk:TADM2E 4.4"
From Algorithm Wiki
m |
Landisdesign (talk | contribs) |
||
| (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). | ||
| + | |||
| 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. | ||
| + | |||
| + | ''Any stable source can do'' looks inaccurate to me. Insert and selection are O(n^2). Bucket sort and the variant at the top seem the only ways to do it in O(n). | ||
Latest revision as of 00:12, 21 November 2019
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.
Any stable source can do looks inaccurate to me. Insert and selection are O(n^2). Bucket sort and the variant at the top seem the only ways to do it in O(n).
