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);   

}

No comments:

Post a Comment