Given an array with random 0,1 ,sort 0's to left and 1's to right???
in time complexity O(n)..
main()
{
int i = 0;
int arr[]={1,1,0,1,0,1,0,0,1};
int size = 9;
int oneP=0;
int zeroP=0;
while(oneP lessThan size && zeroP lessThan size)
{
if(arr[zeroP] == 0 )
{
zeroP++;
oneP++;
continue;
}
if(arr[oneP] == 0)
{
arr[zeroP] = 0;
arr[oneP] = 1;
zeroP++;
}
oneP++;
}
for(i=0;i lessThan size;i++)
printf("arr[%d]= %d\n",i,arr[i]);
}
This method is good but here you are using two variables and worse is that you are traversing array twice.
ReplyDeleteALternative method is based on Quicksort implementation
voidSortSuccessiveOneZero(int iArr[],int iLower, int iUpper)
{
while(iLower < iUpper)
{ while(iArr[iLower] == 0) && (iLower < iUpper)
{ iLower++; }
while(iArr[iUpper] == 1) && iUpper > iLower)
{ iUpper--;}
if(iLower < iUpper)
{ Swap(iArr[iLower],iArr[iUpper]);
}
}
vikrant...first thing i am not traversing the array twice...I am using the second traversal to print it and has nothing to deal with the array sorting... I hope you got the intention.
ReplyDeleteQuick sort is also a valid approach.