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

0 votes
0 votes
The size of array = n.

If the number of negative values = number of positive values, then number of exchange required = n/2.

In worst case, there must exist a positive value and (n-1) negative number.  (If all numbers are negative then sorting is not mandatory). Hence the number of exchange required = (n-1)l
–3 votes
–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
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 $...