The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 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

- $n-1$
- $n$
- $n+1$
- None of the above

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

http://gatecse.in/wiki/Moving_Negative_Numbers_to_the_Beginning_of_Array

+2

@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.

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.

0

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:

http://gatecse.in/wiki/Moving_Negative_Numbers_to_the_Beginning_of_Array

Pls verify.

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.

–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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,470 answers

145,581 comments

62,234 users