MOCK TEST

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

answer given is a)

Answer 1

Yes, $n-1$ does seem correct in the worst case.

Have a look at this code:

int main(int argc, char const *argv[])
{
    int arr[] = {-12, 11, 0, -5, 6, -7, 5, -3, -6};
    int n = sizeof(arr) / sizeof(arr[0]);

    int i = 0, j = 0;

    while(j < n){
        if(arr[j] < 0) swap(arr[i++], arr[j++]);
        else j++;
    }

    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

This does what you are looking for in $O(n)$ time.