Friday, April 9, 2010

Quick Sort and Binary Searching

// Problem Description is compare two integer arrays and find which value is not available in first array

#include < stdio.h >
#include < conio.h >
void quicksort(int elements[],int maxsize);
void sort(int elements[],int left,int right);
int main()
{
     int a[100],b[100],i,j,n,n1,low,high,mid;
     bool found=false;
     printf("\n Enter the number of elements in A : ");
     scanf("%d",&n);
     printf("\n Enter the elements in A : ");
     for(i=0;i < n; i++)
                     scanf("%d",&a[i]);   
     printf("\n Enter the number of elements in B : ");
     scanf("%d",&n1);
     printf("\n Enter the elements in B  : ");
     for(i=0;i < n1 ; i++)
                     scanf("%d",&b[i]);
     quicksort(a,n);
     printf("\n Output \n");
     for(i=0;i < n1 ; i++)
     {
               low=0;
               high=n;
               found=false;
               while(low<=high && !found)
               {
                               mid=(low+high)/2;
                              if(a[mid] == b[i])
                              {
                                          found = true;
                              }
                              else
                              {
                                          if(a[mid] > b[i])
                                               high = mid -1;
                                          else
                                               low = mid + 1;
                             
                              }
               }
               if(!found)
                         printf(" %d ", b[i]);
                       
      }
      getch();
    
}
void quicksort(int elements[], int maxsize)
{
     sort(elements, 0, maxsize - 1);
}
void sort(int elements[],int left,int right)
{
     int pivot, l, r;
     l = left;
     r = right;
     pivot = elements[left];
     while (left < right)
     {
      while ((elements[right] >= pivot) && (left < right))
            right--;
      if (left != right)
      {
         elements[left] = elements[right];
         left++;
      }
      while ((elements[left] <= pivot) && (left < right))
            left++;
      if (left != right)
      {
               elements[right] = elements[left];
               right--;
      }
    }
    elements[left] = pivot;
    pivot = left;
    left = l;
    right = r;
    if (left < pivot)
       sort(elements, left, pivot - 1);
    if (right > pivot)
       sort(elements, pivot + 1, right);   

}

Monday, April 5, 2010

Addition of Two 100 digit Number Program

#include < stdio.h >
#include < conio.h >
#include < string.h >
int main()
{
    char first[100],second[100];


    // here i use 100 digit if u use more than 100 then change the size

    int flength,slength,remain=0,fdata,sdata,i,ans,r1,s;
    clrscr();
    // Gather input from user first and second number
    printf("\n Enter the first number : ");
    scanf("%s",first);
    // Handle the input as a string then only you can store lot of digits
    printf("\n Enter the second number : ");
    scanf("%s",second);
    // Find the length of first and second string
    flength=strlen(first);
    slength=strlen(second);
    s=flength-slength;
    // find the difference between two strings
    if(s!=0)
    {
            printf("\n Enter the both digits are same ");          
    }
    // if both strings length are same then execute the following code
   else
   {
            for(i=flength-1;i>=0;i--)
           {      
                           // convert character to integer
                            fdata=(int)first[i]-48;
                           sdata=(int)second[i]-48;
                          // addition of two numbers
                           ans=remain+fdata+sdata;
                         // find the remain it will goto next step (1 or 0)
                           if(ans>=10)
                          {
                                      ans=ans-10;
                                      remain=1;          
                          }
                         else
                         {
                                     remain=0;
                         }
                         if(i==0)
                        {
                                    r1=remain;    
                        }
                        // answer back store as a character in second arrary
                       // because reduce memory occupation here use second input also used for
                      // output storage variable
                   
                       second[i]=(char)ans+48;
                               
         }         
     // print the answer
     printf("Answer : %d%s",r1,second);
   
  }  
 getch();
}