Geeksforgeeks Array

Question

Consider an array consisting of –ve and +ve numbers. What would be the worst time comparisons an algorithm can take in order to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?

(A)	N-1
(B)	N
(C)	N+1
(D)	(N*(N-1))/2

Comments

Two solutions:

(1) will take N if we compare all elements with 0 and partition the elements.

(2) will take N-1 if we compare elements on the bases of sign i.e. compare 1st two elements and check there sign if both are same then put in one partition and compare 1st and 3rd element and check sign again...