Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 58: | Line 58: | ||
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 or <math>n/2</math> negative numbers. | 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 or <math>n/2</math> negative numbers. | ||
</div> | </div> | ||
| − | <div class="mw-customtoggle-code " style="color:blue;width:60px">Solution</div> | + | <div class="mw-customtoggle-code " style="color:blue;background-color:red;width:60px">Solution</div> |
{{Template:FBD}} | {{Template:FBD}} | ||
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 <math>\theta(n)</math>
No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math>
<syntaxhighlight lang="c" name="negative_positive">
int main() {
GATECSE 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>
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 or <math>n/2</math> negative numbers.
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 <math>\theta(n)</math>
No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math>
<syntaxhighlight lang="c" name="negative_positive">
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>
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 or <math>n/2</math> negative numbers.