FIBONACCI SEARCH WITHOUT RECURSION

FIBONACCI   SEARCH WITHOUT RECURSION BY USING  C PROGRAM

Program:

#include<stdio.h>

void main()

{

   int a[50],i,n,key,loc,fk,p,q,r,m;

   clrscr();

   printf("enter number of elements to be entered");

   scanf("%d",&n);

   printf("enter elements");

   for(i=1;i<=n;i++)

   scanf("%d",&a[i]);

   printf("enter the key element to search");

   scanf("%d",&key);

   fk=fib(n+1);

   p=fib(fk);

   q=fib(p);

   r=fib(q);

   m=(n+1)-(p+q);

   if(key<a[p])

   p=p+m;

   loc=fibsearch(a,p,q,r,key);

   if(loc==0)

     printf("the key is not found");

   else

   printf("%d is found at %d",key,loc);

   getch(); 

}

int fib(int m)

{

   int a,b,c;

   a=0;

   b=1;

   c=a+b;

   while(c<m)

   {

   a=b;

   b=c;

   c=a+b;

   }

   return b;

}

int fibsearch(int a[],int p,int q,int r,int key)

{

   int t;

   while(p!=0)

   {

   if(key==a[p])

   return p;

   else if(key<a[p])

   {

   if(r==0)

   p=0;

   else

   {

   p=p-r;

   t=q;

   q=r;

   r=t-r;

   }

    }

    else

    {

   if(q==1)

   p=0;

   else

   {

   p=p+r;

   q=q-r;

   r=r-q;

   }

    }

   }

   return 0;

}

output:

FIBONACCI SEARCH WITH RECURSION

FIBONACCI  SEARCH WITH RECURSION BY USING               C PROGRAM

Program:

#include<stdio.h>

void main()

{

  int n,a[50],i,key,loc,p,q,r,m,fk;

  clrscr();

  printf("\nenter number elements to be entered");

  scanf("%d",&n);

  printf("enter elements");

  for(i=1;i<=n;i++)

  scanf("%d",&a[i]);

  printf("enter the key element");

  scanf("%d",&key);

  fk=fib(n+1);

  p=fib(fk);

  q=fib(p);

  r=fib(q) ;

  m=(n+1)-(p+q);

  if(key>a[p])

  p=p+m;

  loc=rfibsearch(a,n,p,q,r,key);

  if(loc==0)

  printf("key is not found");

  else

  printf("%d is found at location %d",key,loc);

  getch();

}

int fib(int m)

{

  int a,b,c;

  a=0;

  b=1;

  c=a+b;

  while(c<m)

  {

  a=b;

  b=c;

  c=a+b;

  }

  return b;

}

int rfibsearch(int a[],int n,int p,int q,int r,int key)

{

  int t;

  if(p<1||p>n)

  return 0;

  else if(key==a[p])

  return p;

  else if(key<a[p])

 {

  if(r==0)

  return 0;

  else

  {

  p=p-r;

  t=q;

  q=r;

  r=t-r;

  return rfibsearch(a,n,p,q,r,key);

  }

  }

  else

  {

  if(q==1)

    return 0;

  else

  {

  p=p+r;

  q=q-r;

  r=r-q;

  return rfibsearch(a,n,p,q,r,key);

  }

  }

}

QUICK SORT with c-program

Aim : To Implement Quick Sort Using C program

Program:

#include<stdio.h>

int a[50];

void main()

{

     int i,n;

     clrscr();

     printf(" Enter no of elements to be entered");

     scanf("%d",&n);

     printf("\n Enter elements");

     for(i=1;i<=n;i++)

            scanf("%d",&a[i]);

     quicksort(1,n);

     printf("\nElements after sorting");

     for(i=1;i<=n;i++)

printf("%d ",a[i]);

     getch();

}

int quicksort(int low,int high)

{

      int j;

      if(low<high)

     {

             j=partition(low,high);

            quicksort(low,j-1);

            quicksort(j+1,high);

      }

     return;

}

int partition(int low,int high)

{

        int i,j,temp,pivot;

        i=low;

        j=high+1;

        pivot=a[low];

        while(i<j)

       {

               do

              {

                      i=i+1;

               }while(i<high && pivot>=a[i]);

              do

              {

                      j=j-1;

              }while(j>low && pivot<=a[j]);

            if(i<j)

           {

                   temp=a[i];

                   a[i]=a[j];

                   a[j]=temp;

            }

       }

      a[low]=a[j];

      a[j]=pivot;

     return j;

}

Output:

MERGE SORT USING C PROGRAM

Aim: Merge Sort Using C program

Program:

#include<stdio.h>

void main()

{

 int i,a[50],n;

 clrscr();

 printf(" Enter no of elements to be entered");

 scanf("%d",&n);

 printf(" Enter elements");

 for(i=1;i<=n;i++)

  scanf("%d",&a[i]);

 mergesort(a,1,n);

 printf(" Merge sort=");

 for(i=1;i<=n;i++)

  printf("%d ",a[i]);

 getch();

}

int mergesort(int a[],int low,int high)

{

 int mid;

 if(low<high)

 {

  mid=(low+high)/2;

  mergesort(a,low,mid);

  mergesort(a,mid+1,high);

  merge(a,low,mid,high);

 }

 return;

}

int merge(int a[],int low,int mid,int high)

{

 int i,j,k,l,b[50];

 i=low;

 j=mid+1;

 k=low;

 while(i<=mid&&j<=high)

 {

  if(a[i]<a[j])

  {

   b[k]=a[i];

   i++;

  }

  else

  {

   b[k]=a[j];

   j++;

  }

  k++;

 }

 if(i>mid)

 {

  for(l=j;l<=high;l++)

  {

   b[k]=a[l];

   k++;

  }

 }

 else

 {

  for(l=i;l<=mid;l++)

  {

   b[k]=a[l];

   k++;

  }

  for(l=low;l<=high;l++)

  {

   a[l]=b[l];

  }

 }

}

Merge Sort:

Merge sort is an algorithm that has a fairly efficient space time complexity -

O(n log n) and is fairly trivial to implement. The algorithm is based on splitting

a list, into two similar sized lists (left, and right) and sorting each list and then

merging the sorted lists back together.

Note: the function MergeOrdered simply takes two ordered lists and makes

them one.

Output:

Insertion sorting cprogram

Aim : To write Insertion Sorting Program in C program

 

Program:

#include<stdio.h>

void main()

{

  int a[50],n,i;

  clrscr();

  printf("\n Enter no of elements to be entered");

  scanf("%d",&n);

  printf(" Enter elements");

  for(i=1;i<=n;i++)

    scanf("%d",&a[i]);

  insort(a,n);

  printf(" Insertion sorting");

  for(i=1;i<=n;i++)

     printf(" %d",a[i]);

  getch();

}

insort(int a[],int n)

{

  int k,ele,loc;

  for(k=2;k<=n;k++)

  {

     ele=a[k];

     loc=k-1;

     while(loc>=1&&ele<a[loc])

     {

a[loc+1]=a[loc];

loc=loc-1;

     }

     a[loc+1]=ele;

   }

}

Output :

binary search without recursion

Binary search without recursion c program

Program:

#include<stdio.h>

void main()

{

   int a[50],n,i,key,f;

   clrscr();

   printf("enter no of elements to be entered");

   scanf("%d",&n);

   printf("enter elements ");

   for(i=1;i<=n;i++)

       scanf("%d",&a[i]);

   printf("enter the key to search");

   scanf("%d",&key);

   f=bsearch(a,n,key);

   if(f==0)

       printf("the key not found");

   else

       printf("the %d is found at %d",key,f);

   getch();

}

int bsearch(int a[],int n,int key)

{

   int low=1,high=n,mid;

   while(low<=high)

   {

        mid=(low+high)/2;

        if(key==a[mid])

            return mid;

        else if(key>a[mid])

            low=mid+1;

        else

            high=mid+1;

    }

return 0;

}

Output: 

Towers of hanoic cprogram

TOWERS OF HANOIC CPROGRAM WITH RECURSION

#include<stdio.h>

void main()

{

int n;

clrscr();

printf("enter no of disks=");

scanf("%d",&n);

towersofhanoi(n,'A','B','C');

getch();

}

int towersofhanoi(int n,char source,char dest,char inter)

{

if(n>=1)

{

towersofhanoi(n-1,source,inter,dest);

printf("\nmove disk from %c to tower %c ",source,dest);

towersofhanoi(n-1,inter,dest,source);

}

}

Binary search with recursion

Binary Search With Recursion Using C program

Program:

#include<stdio.h>

void main()

{

   int a[50],n,i,key,f;

   clrscr();

   printf("enter no of elements to be entered");

   scanf("%d",&n);

   printf("enter elements ");

   for(i=1;i<=n;i++)

      scanf("%d",&a[i]);

   printf("enter the key to search");

   scanf("%d",&key);

   f=bsearch(a,n,key);

   if(f==0)

      printf("the key not found");

   else

      printf("the %d is found at %d",key,f);

   getch();

}

int bsearch(int a[],int n,int key)

{

   int low=1,high=n,mid;

   while(low<=high)

   {

      mid=(low+high)/2;

      if(key==a[mid])

          return mid;

      else if(key>a[mid])

          low=mid+1;

      else

          high=mid+1;

    }

    return 0;

}

Output:

2's complement

#include<stdio.h>

2's complement cprogram

#include<string.h>
void main()
{
char b[20];
int i,j,l;
clrscr();
printf("Enter a binary num");
scanf("%s",b);
l=strlen(b);
for(i=l-1;i>=0;i--)
{
if(b[i]=='1')
{
for(j=i-1;j>=0;j--)
{
if(b[j]=='1')
b[j]='0';
else
b[j]='1';
}
}
}
printf("2's compliment is %s",b);
getch();
}

Bubblesort in program c program - Bubblesort program in data structures

Aim: To write a Bubble Sort Program using C program

Program :

#include<stdio.h>

void main()

{

       int a[20],n,i;

       clrscr();

       printf(" Enter the size of the list");

       scanf("%d",&n);

       printf(" Enter the elements :");

       for(i=0;i<n;i++)

   scanf("%d",&a[i]);

       bubblesort(a,n); //sort the elements using bubble sort

       printf(" Bubble sort");

       for(i=0;i<n;i++)

printf(" %d",a[i]);

       getch();

}

bubblesort(int a[],int n)

{

      int i,j,temp;

      for(i=0;i<n-1;i++)

      {

    for(j=0;j<n-i-1;j++)

    {

    if(a[j] > a[j+1])

   {

   temp=a[j];

    a[j]=a[j+1];

    a[j+1]=temp;

    }

    }

      }

 }

Output:

linear search without recursion

Linear Search Without Recursion Using C Program

Program:

#include<stdio.h>

void main()

{

    int a[50],n,f,key,i;

    clrscr();

    printf("enter no of elements to be entered");

    scanf("%d",&n);

    printf("enter elements ");

    for(i=1;i<=n;i++)

        scanf("%d",&a[i]);

    printf("enter the key value to find");

    scanf("%d",&key);

    f=lsearch(a,n,key);

    if(f==0)

       printf("the key not found");

    else

       printf("the %d is found at %d",key,f);

    getch();

}

int lsearch(int a[],int n,int key)

{

    int i;

    for(i=1;i<=n;i++)

    {

        if(a[i]==key)

        return i;

    }

    return 0;

}

Output:

Linear search

Linear Search With Recursion Using C program

Program:

#include<stdio.h>

void main()

{

   int n,a[20],i,j,key;

   clrscr();

   printf("enter no of elements to be entered");

   scanf("%d",&n);

   printf("enter elements");

   for(i=1;i<=n;i++)

      scanf("%d",&a[i]);

   printf("enter the key to search");

   scanf("%d",&key);

   j=rlsearch(a,1,n,key);

   if(j==0)

       printf("the element is not found");

   else

       printf("the element found at %d",j);

   getch();

}

int rlsearch(int a[],int i,int n,int key)

{

   if(i>n)

      return 0;

   if(a[i]==key)

      return i;

   else 

      return rlsearch(a,i+1,n,key);

}

Output: