Digital Analysis and Algorithm Program
Aim
:- Write a program for the linear search.
Source-code
:-
#include<stdio.h>
void
main()
{
int a[50],n,x,i;
printf("\n ********** LINEAR SEARCH ********** ");
printf("\n\n Enter no of Elements:");
scanf("%d",&n);
printf("\n Enter Elemnets:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n Enter element that you want to search ?:");
scanf("%d",&x);
for(i=0;i<n;i++)
{
if(a[i]==x)
{
printf("\n %d element is found on the position
%d.....!!!",x,i);
}
}
if(i==n)
{
printf("\n Sorry..!!! %d element is not found in Given
Array.....!!!",x);
}
}
Aim
:- Write a program for the Binary search.
Source-code
:-
#include<stdio.h>
void
main()
{
int a[50],n,f,l,x,i,m;
printf("\n ********** BINARY SEARCH ********** ");
printf("\n\n Enter no of Elements:");
scanf("%d",&n);
printf("\n Enter Elemnets:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n Enter element that you want to search ?:");
scanf("%d",&x);
f
= 0;
l
= n - 1;
m
= (f+l)/2;
while( f <= l )
{
if ( a[m] < x )
{
f = m + 1;
}
else if ( a[m] == x )
{
printf("\n %d element is found on the position
%d.....!!!", x, m+1);
break;
}
else
{
l = m - 1;
}
m
= (f + l)/2;
}
if
( f > l )
{
printf("\n Sorry..!!! %d element is not found in Given
Array.....!!!", x);
}
}
Aim
:- Write a program for the Selection Sort.
Source-code
:-
#include<stdio.h>
void
main()
{
int a[50],n,i,j,temp;
printf("\n ********** SELECTION SORT ********** ");
printf("\n\n Enter no of Elements:");
scanf("%d",&n);
printf("\n Enter Elemnets:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
printf("\n\n After %d Iteration:",i);
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
printf("\n %d",a[j]);
}
}
printf("\n After Sorting:\n ");
for(i=0;i<n;i++)
{
printf("\n %d",a[i]);
}
}
Aim
:- Write a program for the Bubble Sort.
Source-code
:-
#include<stdio.h>
void
main()
{
int a[50],n,i,j,temp;
printf("\n ********** BUBBLE SORT ********** ");
printf("\n\n Enter no of Elements:");
scanf("%d",&n);
printf("\n Enter Elemnets:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
printf("\n\n After %d Iteration:",i);
for(j=i+1;j<n;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
printf("\n %d",a[j]);
}
}
printf("\n After Sorting:\n ");
for(i=0;i<n;i++)
{
printf("\n %d",a[i]);
}
}
Aim
:- Write a program for the Insertion Sort.
Source-code
:-
#include<stdio.h>
void
main()
{
Simple Usecase
int a[50],n,i,j,temp;
printf("\n ********** INSERTION SORT ********** ");
printf("\n\n Enter no of Elements:");
scanf("%d",&n);
printf("\n Enter Elemnets:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
printf("\n\n After %d Iteration:",i);
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
printf(" %d",a[j]);
}
a[j+1]=temp;
}
printf("\n After Sorting:\n ");
for(i=0;i<n;i++)
{
printf("\n %d",a[i]);
}
}
Algorithm:
Write an algorithm for selection sort and find
out complexity……also WAP for selection sort.
Write an algorithm for insertion sort and find
out complexity……also WAP for insertion sort.
Write an algorithm for quick sort and find out
complexity……also WAP for quick sort.
Algorithm:
Write an algorithm for merge sort and find out
complexity……also WAP for merge sort.
Algorithm:
Write an algorithm for binary search tree and
find out complexity……also WAP for binary search tree.
.
I.
Write an algorithm for linear search and find
out complexity……also WAP for linear search.
Algorithm:
Step-1: [initialize]
k=0
flag =1
Step-2: repeat step-3 for k=0,1 , 2,…..n-1
Step-3: if 1[k] = element
Flag =0
Output ” successful! Element found at”, k+1,”location”
Step-4: if flag=0
Output ” search is unsuccessful”
Step-5: exit.
Program:-
#include<stdio.h>
#include<conio.h>
void linear_search(int element,int n ,int list[]);
void main()
{
Int
I, j, no, arr [ 10];
clrscr ();
printf(“enter 10 values in
array:”);
for(i=0;i<9;i++)
{
Printf (“\n Enter value :”)
Scanf
(“%d”,& #include<stdio.h>
#include<conio.h>
struct node
{
struct node *left,*right;
int data;
}
*root=null;
void search(struct node*,int);
void main()
{
Printf(“enter number
to be searches:”);
Scanf(“%d”, &n);
Search (root ,n);
getch();
}
void
search(struct node*temp ,int n)
{
if(temp==null)
{
printf(record not
found);
getch();
return;
}
if(temp->data==n)
{
printf(“record
found:%d”, temp->data);
getch();
return;
}
}
else
{
if(temp->data>n)
search(temp->left,
n);
else
search(temp->right,
n);
}
}
arr[i])
}
Printf (“\n Enter the value to be searched:”);
scanf(“%d”,&no);
line_search(no,10,arr);
getch();
}
void line_search(int element,int n,
int list[])
{
int j, flag=0;
for(j=0;j<n; j++);
{
If(list[j]==element)
{
print f(“\n Seach is
Successful:”);
printf(“\n
Element found at location:: %d”, k, element”);
flag=1;
}
}
If(flag==0)
Printf(“\n Search is
unsuccessful”);
}
I.
Write an algorithm for binary search and find
out complexity……also WAP for binary search.
Algorithm:
Step-1:[initialize]
low=0
high=n-1
flag=1
Step-2:
repeat through step-4 while(low<=high)
Step-3:
mid=(low+high)/2
Step-4:if(element<1[mid])then
high=mid-1
else if(element>1[mid])then
low=mid+1
else if(element=1[mid])
Output ”search is successful at”,mid+1,”location”
flag=0
return
Step-5:
if(flag)then
Output” search is unsuccessful”
Step-6: exit
Program:-
#include<stdio.h>
#include<conio.h>
void bubble
sort(int n, Int list[]);
void binary search(int
element,int n, int list[]);
void main()
{
int i, j, arr[10],no;
clrscr();
printf(“\n enter 10 values in array”);
for(i=0;i<=9;i++)
{
printf(“\n enters value:”);
scanf(“%d”,&
arr[i]);
}
bubble sort(10,arr);
printf(“\n sorted list:”);
printf(“\n=======\n”);
for(i=0;i<10;i++);
printf(“\n value: %d”, arr[i]);
for(i=0;i<1;i++);
printf(“\n enter element to search:”);
scanf(“%d”,&no);
binary_search(no,10,arr);
getch();
}
void
bubble_sort(int n ,Int list[])
{
int temp ,i, j;
clrscr();
for(i=0;i<n; I++)
{
for(j=0;j<n-i-1;j++)
{
if(list[j]>list[j+1])
{
temp=list[j]
list[j]=list[j+1];
list[j+1]=temp;
}
}
}
}
void
binary_search(int element,int n, int list[])
{
int high, low, mid, flag=0;
high=n-1;
low=0;
mid=(low+high)/2;
while=(flag!=1 && low<<high)
{
if(element<list[mid])
high=mid-1;
else if(element>list[mid])
low=mid+1;
else if(element==list[mid])
{
printf(“\n search is
successful”);
printf(“\nfound at %d
location: %dmid,element);
flag=1;
}
mid=(low+high)/2;
}
if(flag==0)
printf(“\n
search is unsuccessful:”)
}
Algorithm:
Step-1:
[initialize]
current=0
Step-2:
repeat through step-7 while(current<size)
Step-3:
j=current+1
Step-4: repeat
through step-6 while(j<size)
Step-5:
if(array[current]>array[j])
temp= array[current]
array[current]=array[j]
array[j]=temp
Step-6:
j=j+1
Steps-7:
current=current+1
Step-8: exit
Program:-
#include<stdio.h>
#include<stdlib.h>
void
selection sort(int array[],int size)
{
int temp, current, j;
clrscr();
for(current=0;current<size; current++)
{
for(j=current+1;j<size;
j++)
{
if(array[current]>array[j])
{
temp=array[current];
array[current]=array[j]
array[j]=temp;
}
}
}
}
void
main(void)
{
int values[5],i;
clrscr();
printf(”enter the 5 elements \n”);
for(i=0;i<5;i++)
{
scanf(“%d”,& values[i]);
}
selection sort (values,5);
printf(“\n sorted list is as follows \n”);
for(i=0;i<5;i++)
{
printf(“\n %d”, values[i]);
}
getch();
}
Write an algorithm for bubble sort and find out
complexity……also WAP for bubble sort.
Algorithm:
Step-1:
[initialize]
i=0
Step-2:
[loop for pass]
repeat through step-5 while(i<n)
Step-3:
[initialize counter for internally]
j=0
Step-4:
[loop for pass]
repeat through step-5 while(j<n-i)
Step-5:
[check for exchange]
if(list[j]<list[j-1])
temp=list[j]
list[j]+1]=list[j]
list[j]=temp
Step-6: exit
Program:-
#include<stdio.h>
#include<stdlib.h>
void bubble_sort(int
array[],int size)
{
int values[10],i;
clrscr();
printf(“\n unsorted list is as follows \n”);
for(i=0;i<10;i++)
{
printf(“\n enter
values %d:”,i+1);
scanf(“%d”,&
values[i]);
}
bubble_sort(values,10);
printf(“\n sorted list as follows \n”);
for(i=0,i<10;i++)
printf(“\n values: %d: %d”,i+1,values[i]);
getch();
}
void
bubble_sort(int array[],int size)
{
int temp ,i, j;
clrscr();
for(i=0;i<size; i++)
{
for(j=i+1;j<size; j++)
{
if(array[i]>array[i])
{
temp=array[i];
array[i]=array[j]
array[j]=temp;
}
}
}
}
Algorithm:
Step-1:
[initialize]
l [0]=0
Step-2:
repeat through step-3 to step-5 for i=0,1,….n-1
Step-3:
temp=l[i]
Pointer= i-1
Step-4:
while(temp<l[i])
l [pointer+1]=l[pointer]
Pointer=pointer-1
Step-5: l
[pointer]=temp
Step-6: exit
Program:
#include<stdio.h>
Void main()
{
int A[20],N, Temp ,i, j ;
clrscr();
printf(“\n \t ENTER THE NUMBER OF
TERMS:”);
scanf(“%d”,& N);
printf(“\n \t ENTER THE ELEMENTS
OF THE ARRAY:”);
for(i=0;i<N; i++)
{
Gotoxy(25,11+i);
Scanf(“\n
\t %d”,& A[i]);
}
for(i=1;i<N; i++)
{
Temp=A[i];
J=j-1;
while(Temp<A[j]
&& j>=0)
{
A[j+1]=A[j];
J=j-1;
}
A[j+1]=Temp;
}
printf(“\n \t THE ASCENDING ORDER LIST IS: \n”);
for(i=0;i<N; i++)
printf(“\n \t %d”, A[i]);
getch();
}
I.
|
Step-1:
[initialize]
low=first
high=last
[middle element of the list]
Pivot=array[(low+high)/2]
Step-2: repeat
through step-7 while(low<+high)
Step-3: repeat
step-4 while(array[low]<pivot)
Step-4:
low=low+1
Step-5: repeat
step-6 while(array(high)>pivot)
Step-6:
high=high-1
Step-7:
if(low<=high)
temp=array[low]
array[low]=array[high]
array[high]=temp
low=low+1
high=high+1
step-8:
if(first<high)
quick_sort(array ,first,
high)
step-9:
if(low<last)
quick_sort(array, low ,last)
step-10:
exit .
Program:-
#include<stdio.h>
#include<conio.h>
void
quick_sort(int[],int ,int, int);
void main()
{
int arr[9]
int i, no;
clrscr();
printf(“\n \t enter the no> of elements list:”);
scanf()(”%d”,& no);
for(i=0;i<no;i++)
{
scanf(“%d”,&
arr[i]);
}
quick_sort(arr,no,0,no);
getch();
}
void
quick_sort(int arr[],int size,int first, int last)
{
Int temp, high, low, pivot, I ,no=last;
low=first;
high=last;
pivot=arr[(first+last)/2];
do
{
while(arr[low]<pivot)
low++;
while(arr[high]>pivot)
high--;
if(low<=high)
{
temp=arr[low]
arr[low]=arr[high];
arr[high]=temp;
low++;
high--;
}
}
while(low<=high);
if(first<high)
quick_sort(arr, no, first, high);
if (low<last)
quick_sort(arr, no, low, last);
printf(“\n \t your sorted is as follows \n”);
for(i=0;i<n;i++)
{
printf(“%d”, arr[i]);
}
return;
}
Step-1:
[initialize]
I=0,j=0,k=0
Step-2: repeat
step-3 while ((i<n)and(j<m))
Step-3:
if(list_a[i]<list_b[j])
result_list[k]=list_a[i]
i=i+1
k=k+1
else if (list_a[i]>list_b[j])
result_list[k]=list_b[j]
i=j+1
j=j+1
k=k+1
step-4: [
sizeof list_a is larger than the list_b]
else if(j<m)
step-5: repeat
through step-5 for i=1,i+1,i+2,….i-1
result_list[k]=list[j]
i=i+1
k=k+1
step-6:
[size of list_b is larger than list_a]
else if(j>m)
step-7: repeat
through step-7 for j=1,j+1,j+2,….j-1
result_list[k]=list[j]
j=j+1
k=k+1
step-8:
return
Program:-
#include<stdio.h>
Int a[50],n ,p=0;
main()
{
int i;
printf(”NO OF ELEMENTS:” \n);
scanf((“%d”,& n);
printf(“ENTER THE ELEMENTS:” \n);
for(i=0;i<n;i++)
{
scan(“%d”,& a[i]);
}
msort(0,n-10);
printf(“\n SORTED ARRY: \n”);
for(i=0;i<n;i++)
{
printf(“%d \t, a[i]”);
}
printf(“\n”);
}
void
mergesort(int low, int mid, int high)
{
int I, j ,k, temp[50];
i=low;
j=mid+1;
k=low;
while((i<+mid) && (j<=high))
{
if(a[i]>=a[j])
temp[k++]=a[j++];
else
temp[k++]=a[j+=];
}
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
for(i=low;i<=high;i++)
a[i]=temp[i];
printf(”\n ARRY AFTER PASS %d IS:”,p++);
for(i=0;i<n;i++)
printf(“%d”,a[i]);
}
msort(int
low;int high)
{
int mid;
if(low!=high)
{
mid=((low+high)/2);
msort(low,mid);
msort (mid+1, high);
mergsort(low,mid,high);
}
Algorithm:-
Step 1: [Initializing
flag value]
Flag=0
Step 2: [repeat
through step 3 while node!=NULL]
Step 3: [check for
information]
If
info[node]=info then
Flag=1
Return(flag)
Else if
info<info[node]then
Node=left
child[node]
Else
Node=right_child[node]
Step 4: return(flag)
Program:-
#include<stdio.h>
#include<conio.h>
struct node
{
struct node *left,*right;
int data;
}
*root=null;
void search(struct node*,int);
void main()
{
Printf(“enter number
to be searches:”);
Scanf(“%d”, &n);
Search (root,n);
getch();
}
void search(struct
node*temp ,Int n)
{
if(temp==null)
{
printf(record not
found);
getch();
return;
}
if(temp->data==n)
{
printf(“record
found:%d”,temp->data);
getch();
return;
}
}
else
{
if(temp->data>n)
search(temp->left,n);
else
search(temp->right,
n);
}
}
No comments:
Post a Comment