Moving Negative Numbers to the Beginning of Array Revision as of 14:54, 12 December 2013 by Arjun Suresh (talk | contribs) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Makes positive numbers appear after the negative numbers in an array.

Complexity <math>\theta(n)</math>

No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math>

<syntaxhighlight lang="c">

1. include<stdio.h>

int main() {

       int i, n, pi, ni, count = 0;
       int a[1000];
       printf("Enter size of array: ");
       scanf("%d",&n);
       printf("Enter numbers of array\n");
       for(i=0; i<n; i++)
       {
               scanf("%d",&a[i]);
       }
       ni = n-1;
       while(a[ni] >= 0)
               ni--;
       pi = 0;
       while(a[pi] < 0)
               pi++;
       while(ni > pi)
       {
               int temp = a[pi];
               a[pi] = a[ni];
               a[ni] = temp;
               while(a[ni] >= 0)
                       ni--;
               while(a[pi] < 0)
                       pi++;

       }

       for(i=0; i<n; i++)
       {
               printf("%d ", a[i]);
       }

} </syntaxhighlight>

Solution

We are scanning the array from two ends. We scan for positive numbers from left and negative numbers from right and swaps them. As soon as one of them finishes, the algorithm stops. There are n elements, so there can't be more than n/2 positive numbers or n/2 negative numbers.

Tweet