ISI 2018 -C1

Question

Consider an array of length n consisting only of positive and negative integers.Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers,using O(n) time and only constant amount of extra space.

Answer 1

int i, j = 1
for j = 1 to Arr.length
      key = Arr[j]
      if Arr[j] < 0
          Arr[j] = Arr[i]
          Arr[i] = key
          i++

Answer 2

Maintain two indexes to traverse.Initialize first index left as 0 and second index right as n-1.

Do following while left<right:

1. keep inc index left while there are -ve no at it

2. keep dec index right while there are +ve no at it

3. if left<right then exchange A[left] and A[right]

Void Rearrange(int A[], int n)

{

      int left=0,right=n-1;

     while(let<right)

        {

             if(A[left]<0 && left<right)

                left++;

           elseif(A[right]>0 && left<right)

              right--;

          else

              {

                    if(left<right)

                         {

                         int temp;

                         temp=A[left];

                         A[left]=A[right];

                        A[right]=temp;

                         left++;

                        right--;

               }

          }

    }

}

Time Complexity=O(n)

Space Complexity=O(1)

Note:Please take help from Algorithm book by Narasimha Karumanchi