(i) Suppose you have an array of n elements containing only two distinct keys, t
ID: 3715226 • Letter: #
Question
(i) Suppose you have an array of n elements containing only two distinct keys, true and false . Give an O ( n ) algorithm to rearrange the list so that all false elements precede the true elements. You m ay use only constant extra space.
(ii) Suppose you have an array of n elements containing three distinct keys, true , false , and maybe . Give an O ( n ) algorithm to rearrange the list so that all false elements precede the maybe elements, which in turn precede all true elements. You may use only constant extra space.
Explanation / Answer
I am writting in English hope u can create algorithm from it
I) let's assume that input has n elements with two distinct keys true and false.
Identify true and false keys and store it in temp varables temptrue tempfalse. Counter for either true or false number
Take 2 arrays with size n each.
Compare each element of input array with temptrue & tempfalse and store all false in first array and all true in second array and according increment true or false counter
Continues till end of the input array.
At the end of the loop, combine both arrays using true and false counters
(0 to false counter ) + ( false counter +1 size of n)
In n iterations we can arrange in above order.
Ii) we can use same above algorithm for 3 distincs keys
Take 3 arrays with size n each to store false, maybe and true
2 counters for false and maybe
Identify keys and store it in temp varables
Compare array input with temp variables and stores according based on the results also increment false counter if false is met and maybe counter if maybe is met.
Continues till the end of array.
Using false counter add arraies into single entity
(0, false counter)+(false counter +1 , false counter+ maybe counter) +(false counter+ maybe counter +1, size of n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.