Question

Show what happens at each step when doing the converging pointers algorithm on the following data

0, 0, 14, 0, 23, 19, 0, 6, 0, 81, 0, 5

Show the steps and give the legit value at the end and number of copies done.

Answer 1

The converging pointers algorithm is used to clean up data. This is done by scanning over the list and placing all the zeros in the list to the right side of the list.

We can use 3 variables legit, left, right. Also L for the list.

The initial values are,

legit = n (number of entries in the list)

left = 1

right = n

The scanning starts from left side of the list by checking if left >=right. Also left is incremented by 1 if L_{​​​​​​left}​​ not equals to zero.

First L_{​​​​​​left}​ is to be scanned, which is 0 as we can see.

Next step is to reduce legit by one.

Then L_{​​​​​​right} is being copied to L_{​​​​​​left}​​. Also right = right-1

So, our list will be 5, 0, 14, 0, 33, 19, 0, 6, 0, 81, 0

Now L_​left​​ != 0 so left = left +1.

The above steps are repeated and the list will be,

5, 0, 14, 0, 33, 19, 0, 6, 0, 81

Now L_​left​​ = 0 so left will be the same

The above steps are repeated and the list will be,

5, 81, 14, 0, 33, 19, 0, 6, 0

Now L_​left != 0 so left is incremented and we reached the next 0 element.

We do the same as above and the list will be,

5, 81, 14, 0, 33, 19, 0, 6

Again 0 is found and steps repeated.

5, 81, 14, 6, 33, 19, 0

Now since after the element 6, there are no 0s found. So left will reach the right. So left >= right condition is met.

Next step is to check if L_{​​​​​​left} = 0 and if the condition is true legit=legit - 1

Hence the algorithm stops by producing a list as follows,

5, 81, 14, 6, 33, 19

So the legit value is 6

The copies done are 5