You are given a set of 2n disks that alternate between fille

You are given a set of 2n disks that alternate between filled and unfilled disks (see below for n = 4 You are to transform this arrangement such that all the filled disks are moved to the right and all the unfilled disks are at the left, using only exchanges between immediate neighbors. Write down a brute force algorithm to solve the above problem. What is the complexity of your algorithm? Justify your answer.

Solution

Algorithm:

begin sortFilledUnfilled(diskSequence)

for all disk of diskSequence
if diskSequence[i+1] == \'UnfilledDisk\' and diskSequence[i] == \'FilledDisk\'
       swap(diskSequence[i], diskSequence[i+1])
end if
end for

return diskSequence

end sortFilledUnfilled

Code:

for (int i=0;i<n;i++)
{
   for (int j=0;j<n-1-i;j++)
   {
       if (a[j+1] == \'UnfilledDisk\' && a[j] == \'FilledDisk\')
       {
           swap(a[j],a[j+1]); //swap function will be defined separately to swap the filled and unfilled disk
       }
   }
}

Complexity:

The Complexity of the above program/algorithm is O(n^2). The Algorithm runs 2 loops for parsing the disks as we need to check the adjacent disks. Whenever an unfilled disk is followed by a filled disk it will perform the swap else nothing will be done.
This work will be continued till the outer loop reaches the last disk. As there are two loops being used with each loop parsing the whole sequence of disk till the end, hence each loop will have the complexity of O(n).
Therefore, O(n) x O(n) = O(n^2)