Line 47: Line 47:
  
  
 
+
===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.
  
 
<div class="fb-like" data-layout="standard" data-action="like" data-show-faces="false" data-share="true"></div>
 
<div class="fb-like" data-layout="standard" data-action="like" data-show-faces="false" data-share="true"></div>

Revision as of 14:54, 12 December 2013

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.



blog comments powered by Disqus

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[edit]

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.



blog comments powered by Disqus