Difference between revisions of "Moving Negative Numbers to the Beginning of Array"

(→‎Explanation)
 
(94 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<metadesc>C code to makes positive numbers appear after negative numbers in an array. </metadesc>
 +
'''Given an array of positive and negative numbers, write a program to move the numbers such that all negative numbers appear before positive numbers
 +
'''
  
 +
<!--<div class= "mw-collapsible mw-collapsed" id="mw-customcollapsible-code" >-->
 +
Complexity $\Theta(n)$
  
 +
No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math>
  
−
 
+
<syntaxhighlight lang="c" name="negative_positive">
−
 
+
#include<stdio.h>  
−
<pre>
 
−
 
 
−
#include<stdio.h>
 
 
int main()
 
int main()
 
{
 
{
−
         int i,n,pi,ni, count = 0;
+
         int i, n, pi, ni, count = 0;
 
         int a[1000];
 
         int a[1000];
 
         printf("Enter size of array: ");
 
         printf("Enter size of array: ");
Line 18: Line 21:
 
                 scanf("%d",&a[i]);
 
                 scanf("%d",&a[i]);
 
         }
 
         }
−
         ni =n-1;
+
         ni = n-1;
 +
        /*Making ni point to the rightmost negative number*/
 
         while(a[ni] >= 0)
 
         while(a[ni] >= 0)
 
                 ni--;
 
                 ni--;
 
         pi = 0;
 
         pi = 0;
−
         while(a[pi] <0)
+
        /*Making pi point to the leftmost positive number*/
 +
         while(a[pi] < 0)
 
                 pi++;
 
                 pi++;
−
         while(ni >pi)
+
        /*Looping till either negative or positive numbers exhaust*/
 +
         while(ni > pi)
 
         {
 
         {
 +
                /*Swapping a[ni] and a[pi]*/
 
                 int temp = a[pi];
 
                 int temp = a[pi];
 
                 a[pi] = a[ni];
 
                 a[pi] = a[ni];
 
                 a[ni] = temp;
 
                 a[ni] = temp;
 +
                /*Moving ni leftwards to the next negative number*/
 
                 while(a[ni] >= 0)
 
                 while(a[ni] >= 0)
 
                         ni--;
 
                         ni--;
−
                 while(a[pi] <0)
+
                /*Moving pi rightwards to the next positive number*/
 +
                 while(a[pi] < 0)
 
                         pi++;
 
                         pi++;
  
Line 43: Line 52:
  
 
}
 
}
−
</pre>
+
</syntaxhighlight>
  
 +
===Explanation===
 +
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 <math>n</math> elements, so there canʼt be more than <math>n/2</math> positive numbers and more than <math>n/2</math> negative numbers.
  
 +
<!--<div class="mw-customtoggle-code " style="color:white;background-color:blue;width:60px"> Solution</div>-->
  
−
<syntaxhighlight lang="php">
+
{{Template:FBD}}
−
<?php
+
 
−
    $v = "string";    // sample initialization
+
 
−
?>
+
 
−
html text
+
 
−
<?
+
[[Category:Placement Coding Questions from Arrays]]
−
    echo $v;        // end of php code
 
−
?>
 
−
</syntaxhighlight>
 

Latest revision as of 18:08, 24 September 2014

Given an array of positive and negative numbers, write a program to move the numbers such that all negative numbers appear before positive numbers

Complexity $\Theta(n)$

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

<syntaxhighlight lang="c" name="negative_positive">

  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;
       /*Making ni point to the rightmost negative number*/
       while(a[ni] >= 0)
               ni--;
       pi = 0;
       /*Making pi point to the leftmost positive number*/
       while(a[pi] < 0)
               pi++;
       /*Looping till either negative or positive numbers exhaust*/
       while(ni > pi)
       {
               /*Swapping a[ni] and a[pi]*/
               int temp = a[pi];
               a[pi] = a[ni];
               a[ni] = temp;
               /*Moving ni leftwards to the next negative number*/
               while(a[ni] >= 0)
                       ni--;
               /*Moving pi rightwards to the next positive number*/
               while(a[pi] < 0)
                       pi++;

       }

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


} </syntaxhighlight>

Explanation

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 <math>n</math> elements, so there canʼt be more than <math>n/2</math> positive numbers and more than <math>n/2</math> negative numbers.




blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Moving_Negative_Numbers_to_the_Beginning_of_Array&oldid=4261"




#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 lang="php"> <?php 

   $v = "string";    // sample initialization

?> html text <? 

   echo $v;         // end of php code

?> </syntaxhighlight>