The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 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
asked in Algorithms by Veteran (52k points) | 4.2k views
Logic is similar to Quick sort partition method.

Chhotu by that way (partition method) it wont take minimum exchanges.


@Arjun sir link is not working.

4 Answers

+51 votes
Best answer

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:

int main() {

       int i, n, pi, ni, count = 0;
       int a[1000];
       printf("Enter size of array: ");
       printf("Enter numbers of array\n");
       for(i=0; i<n; i++)
       ni = n-1;
       /*Making ni point to the rightmost negative number*/
       while(a[ni] >= 0)
       pi = 0;
       /*Making pi point to the leftmost positive number*/
       while(a[pi] < 0)
       /*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)
               /*Moving pi rightwards to the next positive number*/
               while(a[pi] < 0)
       for(i=0; i<n; i++)
               printf("%d ", a[i]);

answered by Veteran (406k points)
edited by

can I use simple selection sort instead ? coz it will too lead to a minimum of n/2 exchange.

Is the meaning of exchange and swapping is same?

yes @srestha 

@Arjun Sir what if the array contains negative elements on the first few and last few positions, We can not simply swap them. What to do in this case.

Let Array be,

A [10 -25 -5 -95 -22- 45 12 45 12 87 45 12 45 87 65 31 05 85 -12 -23 -45 -89 -65 -32]
Please Let me know how it can be solved in n/2.

@Rajesh Raj 

Consider an array of elements: -6,-1,-5,-2,-4

Using selection sort(descending) there will be 4 exchanges(more than n/2), but no exchanges are required according to algorithm given here:

Pls verify.


will the answer not change if use some other algorithm?in the ques they did not mention which approach to follow

@srestha  i did not understand question i think.

every elements in array  -ve & +ve value right?

eg ..{2,3,-2,-3}  


no, array maynot contain any -ve number too


link not working

@srestha  ..... means array contain  one -ve number then one exchange , two -ve two exchange........n/2 -ve  n/2  exchange at max.  bcz here we don't  care about ordering means sorting here..... am i right now? 

0 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.
answered by
Why this answer is marked wrong?? I think n-1 is worst case as compared to n/2 as n-1 will always take more time. If we look asymptotically it's O(n). Please explain I am confused
I thought in the same way

please explain
I figured it out the reason it's marked wrong coz question is asking minimum number of comparison. No doubt n-1 will give worst case but it won't give minimum number of comparison.
0 votes
#include <stdio.h>
#include <stdlib.h>

int main()
    int i=0,length;
    printf("Enter input size\n");
    int *arr=(int *)malloc(sizeof(int)*length);
    printf("Enter %d inputs\n",length);
      printf("%d: ",i+1);
    printf("\nInput Given: ");
        printf("%d ",arr[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.

            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);
answered by Active (2.4k points)
edited by
–3 votes
My view : suppose we are given n numbers atored in array. We can use quick sort as in worst case it can arrange all the elements in array in( log n) time.. Run quick sort algo. On Given number and check how many times the swap() function is called in quick sort algo... So count of swap() function in quick sort algo is our minimum no of exchange required to arrange all elemnts in the given array!!! Correct me if wrong. Plzz
answered by Boss (19.9k points)
but the option is      n     n-1       n+1        n(n+1)/2   

then which of the option is correct
quick sort best case time complexity nlogn
What if we apply merge sort?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,093 answers
71,001 users