Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Friday, 14 September 2012

Sort an Array of 0 1& 2 in one pass






#include<stdio.h>

int main()
{
    int A[] = {2,2,2,1,1,1,0,0,0,1,2,0};
    int j,i,x,y,n,t=A[0];
    n=sizeof(A)/sizeof(A[0]);
printf("Size of array : %d\n",n);
    for(x=i=0,y=j=n-1;i<=j;)
    {
        if(t==0)
        {
            A[x]=0;
            x++;
            i++;
            t=A[i];
        }
        else if(t==2)
        {
            t=A[y];
            A[y]=2;
            y--;
            j--;
        }
        else
        {
            i++;
            t=A[i];
        }
    }

    while(x<=y)
    {
        A[x++]=1;
    }

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

Let me know your thoughts.

Wednesday, 4 July 2012

sort an array a[n] containing 0s and 1s with time complexity n and you cant use more than 1 data structure



// TIME: O(n) || Space : O(1)
#include<stdio.h> int main() { int A[20],i,j,n,temp; printf("Enter n :"); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&A[i]); printf("\n--"); i=0; j=n-1; while(i<j) { while(A[i]==0) i++; while(A[j]==1) j--; if(i<j) { temp=A[i]; A[i]=A[j]; A[j]=temp; i++; j--; } }// end of while printf("\n"); for(i=0;i<n;i++) printf("%d ",A[i]); printf("\n"); return 0; }