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 Arrange(disks){
  
   i=0;
   while(i<2n){
      
       if(disks[i] is unfilled){
           j=i-1
           while(disks[j] is filled and j >= 0){
               swap disks[i] and disks[j]
               j = j - 1;
           }
          
       }
       i = i + 1
   }  
  
}

T(n) = 1+0+2+0+3+0+.....n/2

= 1+2+3+4+.....+n/2
= (n/4)(1 + n/2)
= O(n^2)