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

Give the correct matching for the following pairs:

Group - 1

(A) $${\rm O}(\log n)$$
(B) $${\rm O}(n)$$
(C) $${\rm O}(n\log n)$$
(D) $${\rm O}({n^2})$$

Group - 2

(P) Selection
(Q) Insertion sort
(R) Binary search
(S) Merge sort

The correct matching for the following pairs is

A. All pairs shortest path	1. Greedy
B. Quick Sort	2. Depth-First Search
C. Minimum weight spanning tree	3. Dynamic Programming
D. Connected Components	4. Divide and Conquer