edited by
338 views
0 votes
0 votes
Consider an array of length $n$ consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only constant amount of extra space.
edited by

2 Answers

1 votes
1 votes

Lets the array A of size n be given as input (we assume that 0 isnt present as only positive and negative integers are considered)

Swap(x,y) swaps the value of x and y in O(1)

  1. Set int i to 0
  2. while(A[i] < 0) i = i+1; // this is to ensure that i is set to first positive number appearing in array
  3. Set j to i

while(j<n){

if( A[j]<0) {swap(A[i],A[j]); i++;}

else j++;

}

 the loop checks if A[j] is less than 0 or not, when negative it swaps and increments the i which moves to next position and if positive i stays while j is incremented.

this runs till the end of array. the whole algo takes order of n.

0 votes
0 votes
#include<stdio.h>
int main(){
int a[]={-1,5,2,-9,10,8};
int i=0,j=0,n=sizeof(a)/sizeof(int);

while(j<n) {
if(a[i]<a[j]){
int x=a[i];
a[i] = a[j];
a[j] = x;
}
j++;
if(j>=n){
i = i+1;
j=0;
}
if(i==n){
break;
}

}
for (int k = 0; k < n; ++k) {
printf("%d \t", a[k]);
}
}

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4
admin asked Aug 8, 2022
382 views
Consider a stack machine where the only available workspace is a stack whose elements are unsigned integers. We will denote the configuration of the stack by a sequence. ...