19,624 views
57 votes
57 votes

Suppose we want to arrange the $n$ numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

  1. $n-1$
  2. $n$
  3. $n+1$
  4. None of the above

6 Answers

Best answer
89 votes
89 votes

Answer is (D) None of these.

We just require $n/2$ swaps in the worst case. The algorithm is as given below:

Find positive number from left side and negative number from right side and do exchange. Since, at least one of them must be less than or equal to $n/2$, there cannot be more than $n/2$ exchanges. An implementation is given below:

#include<stdio.h>
int main() {

       int i, n, pi, ni, count = 0;
       int a[1000];
       printf("Enter size of array: ");
       scanf("%d",&n);
       printf("Enter numbers of array\n");
       for(i=0; i<n; i++)
       {
               scanf("%d",&a[i]);
       }
       ni = n-1;
       /*Making ni point to the rightmost negative number*/
       while(a[ni] >= 0)
               ni--;
       pi = 0;
       /*Making pi point to the leftmost positive number*/
       while(a[pi] < 0)
               pi++;
       /*Looping till either negative or positive numbers exhaust*/
       while(ni > pi)
       {
               /*Swapping a[ni] and a[pi]*/
               int temp = a[pi];
               a[pi] = a[ni];
               a[ni] = temp;
               /*Moving ni leftwards to the next negative number*/
               while(a[ni] >= 0)
                       ni--;
               /*Moving pi rightwards to the next positive number*/
               while(a[pi] < 0)
                       pi++;
       }
       for(i=0; i<n; i++)
       {
               printf("%d ", a[i]);
       }

}
edited by
2 votes
2 votes
it would be n-1 in a worst case, n is never the case because if all are -ve number then there is no exchange. But in worst case array is like 1,-1,-2,-3,-4.... so total n-1 exchange are needed.
1 votes
1 votes
#include<stdio.h>
int main() {
 
       int i, n, pi, ni, count = 0;
       int a[1000];
       printf("Enter size of array: ");
       scanf("%d",&n);
       printf("Enter numbers of array\n");
       for(i=0; i<n; i++)
       {
               scanf("%d",&a[i]);
       }
       ni = n-1;
       pi = 0;
       while(ni >= pi)
       {
               if((a[pi]>=0) && (a[ni]<0))
               {
                   int temp = a[pi];
                   a[pi] = a[ni];
                   a[ni] = temp;
                   pi++;ni--;
               }
               else if((a[pi]>=0) && (a[ni]>=0))
               {
                 ni--;
               }
               else if((a[pi]<0) && (a[ni]<0))
               {
                 pi++;
               }
               else if((a[pi]<0) && (a[ni]>=0))
               {
                  pi++;ni--;
               }
       }
       for(i=0; i<n; i++)
       {
               printf("%d ", a[i]);
       }
 
}

We can simply apply merge algorithm concept and it will take O(n) time complexity and maximum n/2 swaps are required.

0 votes
0 votes
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i=0,length;
    printf("Enter input size\n");
    scanf("%d",&length);
    int *arr=(int *)malloc(sizeof(int)*length);
    printf("Enter %d inputs\n",length);
    for(i=0;i<length;i++){
      printf("%d: ",i+1);
      scanf("%d",(arr+i));
    }
    printf("\nInput Given: ");
    for(i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    moveAllNegativesAtLeft(arr,length);
    printf("\nOutput:");
    for(i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

void moveAllNegativesAtLeft(int *arr,int length){
    int left=0,right=length-1,temp,nofExch=0;

    // While Loop Invariants:
          //1. If left>0 then, Arr[0] to Arr[left-1] are all negative numbers

         //2. If right<length-1 then, Arr[right-1] to Arr[length-1] are all positive numbers.

    while(left<right){   
        for(;left<length;left++){
            if(arr[left]>=0)
                break;
        }
        for(;right>=0;right--){
            if(arr[right]<0)
                break;
        }
        if(left<right){
            temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
            right--;
            left++;             //After each exchange right variable decreases by one
            nofExch++;    //and left variable increases by one
                                 //and while loop runs until left<right, hence at max n/2 exchanges are possible
        }

    }
    printf("\nTotal Number of Exchanges: %d",nofExch);
}
edited by
Answer:

Related questions

30 votes
30 votes
5 answers
1
Kathleen asked Sep 23, 2014
9,015 views
If $n$ is a power of $2$, then the minimum number of multiplications needed to compute $a^n$ is$\log_2 n$$\sqrt n$$n-1$$n$
41 votes
41 votes
3 answers
2
48 votes
48 votes
2 answers
3
Kathleen asked Sep 23, 2014
22,542 views
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$then the o...
31 votes
31 votes
3 answers
4
Kathleen asked Sep 23, 2014
5,076 views
Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $...