Suppose that an array A consists of n elements, each of which is red, white, or

Question

Suppose that an array A consists of n elements, each of which is red, white, or blue. We seek to sort the elements so that all the reds come before all the whites, which come before all the blues. The only operation permitted on the keys are
Examine(A, i) - report the color of the i-th element of A
Swap(A, i, j) - swap the i-th element of A with the j-th element
Find a correct and efficient algorithm for red-white-blue sorting. There is a linear-time solution.


Plz provide the algorithm, and its correctness, and analysis of running time.

Explanation / Answer

Here is your solution:

http://i54.tinypic.com/4qrclf.jpg

http://i55.tinypic.com/2ur86tu.jpg

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.