The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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 (59.4k points) | 2.8k views
Logic is similar to Quick sort partition method.

3 Answers

+36 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:

answered by Veteran (342k 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 

–1 vote
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
–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 (20.4k 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

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

35,506 questions
42,827 answers
42,181 users