This shows you the differences between two versions of the page.

algorithms._design_and_analysis:sorting:water_jugs [2013/09/19 00:47] julia created |
algorithms._design_and_analysis:sorting:water_jugs [2013/09/19 00:48] (current) julia |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | Problem Statement: | + | **Problem Statement:** |

Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa. | Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa. | ||

Line 8: | Line 8: | ||

- | Solution: | + | **Complexity:** |

- | n log(n) | + | |

- | PseudoCode: | + | * n log(n) |

+ | | ||

+ | **PseudoCode:** | ||

Take the element from first array and partition the second according to that element. Partition the first array according to that element in array 2. | Take the element from first array and partition the second according to that element. Partition the first array according to that element in array 2. | ||

Do the same with left part and right recursively until all element in the place. | Do the same with left part and right recursively until all element in the place. | ||

- | Implementation: | + | **Implementation:** |

Coming soon... | Coming soon... |

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported