DIJKSRTRA'S ALGORITHM

/*Implementation of Shortest Path Algorithm(DIJKSRTRA's ALGORITHM) in C*/

#include< stdio.h>
#include< conio.h>
#include< process.h>
#include< string.h>
#include< math.h>
#define IN 99
#define N 6

int dijkstra(int cost[][N], int source, int target);

void main()
{
int cost[N][N],i,j,w,ch,co;
int source, target,x,y;
clrscr();
printf("\tShortest Path Algorithm(DIJKSRTRA's ALGORITHM\n\n");
for(i=1;i< N;i++)
for(j=1;j< N;j++)
cost[i][j] = IN;
for(x=1;x< N;x++)
{
for(y=x+1;y< N;y++)
{
printf("Enter the weight of the path between node %d and %d: ",x,y);
scanf("%d",&w);
cost [x][y] = cost[y][x] = w;
}
printf("\n");
}
printf("\nEnter The Source:");
scanf("%d", &source);
printf("\nEnter The target");
scanf("%d", &target);
co = dijsktra(cost,source,target);
printf("\nShortest Path: %d",co);
getch();
}

int dijsktra(int cost[][N],int source,int target)
{
int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
char path[N];
for(i=1;i< N;i++)
{
dist[i] = IN;
prev[i] = -1;
}
start = source;
selected[start]=1;
dist[start] = 0;
while(selected[target] ==0)
{
min = IN;
m = 0;
for(i=1;i< N;i++)
{
d = dist[start] +cost[start][i];
if(d< dist[i]&&selected[i]==0)
{
dist[i] = d;
prev[i] = start;
}
if(min>dist[i] && selected[i]==0)
{
min = dist[i];
m = i;
}
}
start = m;
selected[start] = 1;
}
start = target;
j = 0;
while(start != -1)
{
path[j++] = start+65;
start = prev[start];
}
path[j]='\0';
strrev(path);
printf("%s", path);
return dist[target];
}
/***** Output *********

Shortest Path Algorithm(DIJKSRTRA's ALGORITHM

Enter the weight of the path between node 1 and 2: 2
Enter the weight of the path between node 1 and 3: 3
Enter the weight of the path between node 1 and 4: 4
Enter the weight of the path between node 1 and 5: 5

Enter the weight of the path between node 2 and 3: 5
Enter the weight of the path between node 2 and 4: 2
Enter the weight of the path between node 2 and 5: 3

Enter the weight of the path between node 3 and 4: 1
Enter the weight of the path between node 3 and 5: 4

Enter the weight of the path between node 4 and 5: 5



Enter The Source:2

Enter The target4
CE
Shortest Path: 2
*/

Bubble Sort

/**** C Program For Implementation Of Bubble Sort. Sorting names entered by the user *****/
#include< stdio.h>
#include< conio.h>
#define MAX 10

char name[MAX][15];
void sort(int n)
{
int pa,cp,i,j,k,kk=0;
char temp[15];
pa=n-1;
cp=n-1;
for(i=1;i< =pa;i++)
{
for(j=1;j< =cp;j++)
{
kk=kk+1;
if(strcmp(name[j],name[j+1])>0)
{
strcpy(temp,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],temp);
}
}
printf("\n List after %d pass is ",i);
for(k=1;k< =n;k++)
printf("\n\t\t %s",name[k]);
getch();
}
clrscr();
printf("\n\t\t Total Comparisions Done : %d",kk);
}

void main()
{
int n,i,j;
clrscr();
printf("Enter How Many Names : ");
scanf("%d",&n);
if(n>MAX)
printf("\n\t\tArray Size IS Only %d",MAX);
else
{
printf("\n\t\tEnter %d Names :\n",n);
for(i=1;i< =n;i++)
{
printf("\t\t");
scanf("%s",name[i]);
}
sort(n);
printf("\n\n\t\tSorted List ");
for(i=1;i< =n;i++)
printf("\n\t\t%s",name[i]);
}
getch();
}
/********************* OUTPUT *******************
Enter How Many Names : 4

Enter 4 Names :
Malcolm
Lionel
Mayank
Pinto

List after 1 pass is
Lionel
Malcolm
Mayank
Pinto
List after 2 pass is
Lionel
Malcolm
Mayank
Pinto
List after 3 pass is
Lionel
Malcolm
Mayank
Pinto

*/

Binary Search Tree

/* C Program on binary Search Tree */

#include< stdio.h>
#include< conio.h>
#include< string.h>
#include< dos.h>
#include< stdlib.h>

struct node
{
char data[15];
struct node *left,*right;
};

void insert(struct node *r,struct node *p)
{
if((r->right==NULL)&&(strcmp(p->data,r->data)>0))
r->right=p;
else if((r->right!=NULL)&&(strcmp(p->data,r->data)>0))
insert(r->right,p);
if((r->left==NULL)&&(strcmp(p->data,r->data)< 0))
r->left=p;
else if((r->left!=NULL)&&(strcmp(p->data,r->data)< 0))
insert(r->left,p);

}

void tree(struct node *r,int c)
{
int top,flag;
struct node *w,*stack[20];
if(r!=NULL)
{
if(c!=4)
{
if(c == 1)
printf(" %s ",r->data);
tree(r->left,c);
if(c == 2)
printf(" %s ",r->data);
tree(r->right,c);
if(c == 3)
printf(" %s ",r->data);
}
}
if(c == 4)
{
top = 0;
w = r;
flag = 0;
while((top != -1)&&(w!=NULL))
{
while((flag == 0) && (w->left!=NULL))
{
stack[top] = w;
top++;
w = w->left;
}
printf(" %s ",w->data);
if(w->right != NULL)
{
w = w->right;
flag = 0;
}
else
{
top--;
w = stack[top];
flag = 1;
}
}
}
}
void main()
{
int choice,c,i,flag;
char temp='N',temp1[15];
struct node *s,*root,*r,*q;
root = NULL;
do
{
clrscr();
printf("\n 1. Enter");
printf("\n 2. Delete ");
printf("\n 3. Search ");
printf("\n 4. Display");
printf("\n 5. Exit");
printf("\nEnter Your Choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("***** Data Entry ***** ");
do
{
s=malloc(sizeof(struct node));
s->left=NULL;
s->right=NULL;
printf("\nEnter Data : ");
scanf("%s",&s->data);
if(root==NULL)
root=s;
else
insert(root,s);
printf("\nEnter Your Elements[y/n] : ");
scanf("%c",&temp);
}
while(temp=='y');
break;

case 2:printf("****** Delete Operation *******\n");
do
{
printf("\nEnter Element To Be Deleted : ");
scanf("%s",temp1);
s=root;i=0;flag=0;
do
{
if(strcmp(s->data,temp1)>0)
{
r=s;
s=s->left;
i=2;
}
if(strcmp(s->data,temp1)==0)
{
flag=1;
if(i==0)
{
if(root->right!=NULL)
{
q=root->left;
root=root->right;
insert(root,q);
}
if(root->right==NULL)
root=root->left;
}
else
{
if(i==1)
{
q=s->left;
r->right=s->right;
if(s->left!=NULL)
insert(r,q);
}
if(i==2)
{
q=s->right;
r->left=s->left;
if(s->right!=NULL)
insert(r,q);
}
}
}
}
while(flag==0&&s!=NULL);
printf("\n Delete Any More[Y/N] : ");
scanf("%c",&temp);
}
while(temp=='y');
break;
case 3:printf("****** Search Operation *******\n");
do
{
printf("\n Enter Name To Be Searched");
scanf("%s",temp1);
i=0;
s=root;
while(s!=NULL&&i==0)
{
if(strcmp(s->data,temp1)< 0)
s=s->right;
if(strcmp(s->data,temp1)>0)
s=s->left;
if(strcmp(s->data,temp1)==0)
i=1;
}
if(i==0)
printf("\nElement Not Found\n");
else
printf("\nElement Found\n");
printf("\nEnter More Elements[Y/N] : ");
scanf("%c",&temp);
}
while(temp=='y');
break;
case 4:clrscr();
do
{
clrscr();
printf("\n 1. Preorder\n 2. Inorder \n 3. Postorder \n 4. Non Recursion \n 5. Exit");
printf("\nEnter Your Choice : ");
scanf("%d",&c);
if(root==NULL)
printf("Tree Not Started Yet");
else
tree(root,c);
printf("\n Press Any Key To Continue......");
getch();
}
while(c!=5);
break;
}
}
while(choice!=5);
}
/****************** OUTPUT ****************

1. Enter
2. Delete
3. Search
4. Display
5. Exit
Enter Your Choice : 1
/****** Data Entry *******

Enter Data : Lionel
Enter More Elements(Y/N) : y
Enter Data : Dylan
Enter More Elements(Y/N) : y
Enter Data : Daniel
Enter More Elements(Y/N) : y
Enter Data : Malcolm
Enter More Elements(Y/N) : y
Enter Data : Cyril
Enter More Elements(Y/N) : y
Enter Data : Jason
Enter More Elements(Y/N) : n

1. Enter
2. Delete
3. Search
4. Display
5. Exit
Enter Your Choice : 4

1. Preorder
2. Inorder
3. Postorder
4. Non Recursion
5. Exit
Enter Your Choice : 1
Lionel Dylan Malcolm Cyril Daniel Jason

Press Any Key to Contiue....

1. Preorder
2. Inorder
3. Postorder
4. Non Recursion
5. Exit
Enter Your Choice : 2
Malcolm Cyril Dylan Lionel Jason Daniel

Press Any Key to Contiue....

1. Preorder
2. Inorder
3. Postorder
4. Non Recursion
5. Exit
Enter Your Choice : 3
Cyril Malcolm Dylan Lionel Jason Daniel

Press Any Key to Contiue....

1. Preorder
2. Inorder
3. Postorder
4. Non Recursion
5. Exit
Enter Your Choice : 4
Malcolm Cyril Dylan Lionel Jason Daniel


Press Any Key to Contiue....

1. Preorder
2. Inorder
3. Postorder
4. Non Recursion
5. Exit
Enter Your Choice : 5

Press Any Key To Continue.....

1. Enter
2. Delete
3. Search
4. Display
5. Exit
Enter Your Choice : 3

Enter Name To Be Searched : Dylan
Element Found

Enter More Elements(Y/N) : n

1. Enter
2. Delete
3. Search
4. Display
5. Exit
Enter Your Choice : 2

****** Delete Operation *******
Enter Element To Be Deleted : Dylan
Delete Any More(Y/n) : n

1. Enter
2. Delete
3. Search
4. Display
5. Exit
Enter Your Choice : 5

*/

Heap Sort

/************* C Program To Sort An Array Using Heap Sort *************/

#include < stdio.h>
#include < conio.h>

void swap(int *x,int *y)
{
int temp;
temp=*x;
*x = *y;
*y = temp;
}

void heapsort(int a[],int n)
{
int i,s,f;
for(i=1;i< n;++i)
{
s=i;
f=(s-1)/2;
while( a[f]< a[s])
{
swap(&a[f],&a[s]);
s=f;
if(s==0)
break;
f=(s-1)/2;
}
}
for(i=n-1;i>=1;--i)
{
swap(&a[0],&a[i]);
f=0;
s=1;
if(i==1)
break;
if(i>2)if(a[2]>a[1])s=2;
while( a[f]< a[s] )
{
swap(&a[f],&a[s]);
f=s;
s=2*f+1;
if(i>s+1 )if(a[s+1]>a[s])s=s+1;
if (s>=i)
break;
}
}
}


void main()
{
int a[100],n,i;
clrscr();
printf("\t\tHEAP SORT\n");
printf("\nEnter The Number Of Elements\t: ");
scanf("%d",&n);
printf("\nEnter Elements\n");
for(i=0;i< n;++i)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\n\t\t\tSorted List\n");
for(i=0;i< n;++i)
printf("\t%d",a[i]);
getche();
}
/***************** OUTPUT ******************
HEAP SORT

Enter The Number Of Elements : 6

Enter Elements
45
12
3
1
78
6

Sorted List
1 3 6 12 45 78
*/

Krushkal's Algorithm - 2

/* C Program on Krushkal's Algorithm */

#include< stdio.h>
#include< stdlib.h>
void main()
{
int graph[15][15],s[15],pathestimate[15],mark[15];
int num_of_vertices,source,i,j,u,predecessor[15];
int count=0;
int minimum(int a[],int m[],int k);
void printpath(int,int,int[]);
printf("\nEnter The No. Of Vertices\n");
m scanf("%d",&num_of_vertices);
if(num_of_vertices< =0)
{
printf("\nThis Is Meaningless\n");
exit(1);
}
printf("\nEnter The Adjacent Matrix\n");
for(i=1;i< =num_of_vertices;i++)
{
printf("\nEnter The Elements Of Row %d\n",i);
for(j=1;j< =num_of_vertices;j++)
scanf("%d",&graph[i][j]);
}
printf("\nEnter The Source Vertex\n");
scanf("%d",&source);
for(j=1;j< =num_of_vertices;j++)
{
mark[j] = 0;
pathestimate[j] = 999;
predecessor[j] = 0;
}
pathestimate[source]=0;

while(count< num_of_vertices)
{
u = minimum(pathestimate,mark,num_of_vertices);
s[++count] = u;
mark[u] = 1;
for(i=1;i< =num_of_vertices;i++)
{
if(graph[u][i]>0)
{
if(mark[i]!=1)
{
if(pathestimate[i]>pathestimate[u]+graph[u][i])
{
pathestimate[i] = pathestimate[u]+graph[u][i];
predecessor[i] = u;
}
}
}
}
}
for(i=1;i< =num_of_vertices;i++)
{
printpath(source,i,predecessor);
if(pathestimate[i]!=999)
printf("->(%d)\n",pathestimate[i]);
}
}

int minimum(int a[],int m[],int k)
{
int mi=999;
int i,t;
for(i=1;i< =k;i++)
{
if(m[i]!=1)
{
if(mi>=a[i])
{
mi = a[i];
t = i;
}
}
}
return t;
}

void printpath(int x,int i,int p[])
{
printf("\n");
if(i==x)
printf("%d",x);
else if(p[i]==0)
printf("Number Path From %d To %d",x,i);
else
{
printpath(x,p[i],p);
printf("..%d",i);
}
}
/****************

Enter The No. Of Vertices
6

Enter The Adjacent Matrix

Enter The Elements Of Row 1
0 1 1 1 0 0

Enter The Elements Of Row 2
0 0 1 0 1 0

Enter The Elements Of Row 3
0 0 0 1 1 1

Enter The Elements Of Row 4
0 0 0 0 0 1

Enter The Elements Of Row 5
0 0 0 0 0 1

Enter The Elements Of Row 6
0 0 0 0 0 0

Enter The Source Vertex
1

1->(0)


1..2->(1)


1..3->(1)


1..4->(1)



1..3..5->(2)



1..4..6->(2)

*/

Krushkal's Algorithm

/* C Program On Krushkal's Algorithm */

#include < stdio.h>
#include < conio.h>
typedef struct
{
int node1;
int node2;
int wt;
}edge;

void sortedges(edge a[],int n)
{
int i,j;
edge temp;
for(i=0;i< n-1;++i)
for(j=i+1;j< n;++j)
if(a[i].wt>a[j].wt){temp=a[i];a[i]=a[j];a[j]=temp;}
}

int checkcycle(int p[],int i,int j)
{
int v1,v2;
v1 = i;
v2 = j;
while(p[i]>-1)
i = p[i];
while(p[j]>-1)
j = p[j];
if(i!=j)
{
p[j]=i;
printf("%d %d\n",v1,v2);
return 1;
}
return 0;
}
void main()
{
edge e[100];
int parent[100];
int n,i,j,m,k = 1,cost = 0;
clrscr();
printf("KRUSKAL's ALGORITHM\n");
printf("Enter number of nodes\n");
scanf("%d",&n);
for(i=0;i< n;++i)
parent[i]=-1;
i = 0;
printf("Enter number of edges\n");
scanf("%d",&m);
for(i=0;i< m;++i)
{
printf("enter an edge and wt\n");
scanf("%d %d %d", &e[i].node1,&e[i].node2,&e[i].wt);
}
sortedges(e,m);
printf("\n\nEdges of the tree\n");
i = 0;
while(k< n)
{
if(checkcycle(parent,e[i].node1,e[i].node2))
{
k++;
cost=cost+e[i].wt;
i++;
}
}
printf("cost = %d",cost);
getch();
}

Radix Sort Algorithm

/* C program to sort an array using radix sort LINKED LIST implementation*/

#include < stdio.h>
#include < conio.h>
#include < stdlib.h>

void radix(int a[],int n,int m)
{
typedef struct node
{
int data;
struct node * next;
}NODE;

NODE * ptr,*start,*prev;
NODE *front[10], *rear[10];
int k=1,i,j,y,p;;
/*creating initial linked list*/
start=NULL;
for(i=0;i< n;++i)
{
ptr=(NODE *)malloc(sizeof(NODE));
ptr->data=a[i];
ptr->next=NULL;
if(start==NULL)
start=ptr;
else
prev->next=ptr;
prev=ptr;
}

/*radix sort*/

for(i=1;i< =m;++i)
{
for(j=0;j< 10;++j)
front[j]=NULL;
/*placing elements into queues*/
ptr=start;
while(ptr!=NULL)
{y=ptr->data/k %10;/*y is the digit*/
if(front[y]==NULL)
{
front[y]=ptr;
rear[y]=ptr;
}
else
{
rear[y]->next=ptr;
rear[y]=ptr;
}

ptr=ptr->next;
}

start=NULL;
for(j=0;j< 10;++j)
if(front[j]!=NULL)
{
if(start==NULL)
start=front[j];
else rear[p]->next=front[j];
p=j;
}
rear[p]->next=NULL;
k=k*10;
}
/*copying back to array*/
ptr=start;
for(i=0;i< n;++i,ptr=ptr->next)
a[i]=ptr->data;

}

void main()
{
int a[100],n,i,m;
char temp;
do
{
clrscr();
printf("===========================RADIX SORT===========================================\n");
printf("ENTER NUMBER OF NUMBERS AND NUMBER OF DIGITS\n");
scanf("%d%d",&n,&m);
printf("ENTER ELEMENTS\n");
for(i=0;i< n;++i)
scanf("%d",&a[i]);
radix(a,n,m);
printf("SORTED LIST\n");
for(i=0;i< n;++i)
printf("%d ",a[i]);
printf("\nDO YOU wish to continue?[y/n]\n");
scanf("%c",&temp);


}while(temp=='y'|| temp=='Y');
printf("\n---------------------------------------------------------------------------------\n");
getch();
}
/*OUTPUT:
===========================RADIX SORT===========================================

Enter number of numbers and number of digits
4
2
enter elements
25
65
35
45
sorted list
25 35 45 65
Do you wish to continue?[y/n]
n
--------------------------------------------------------------------------------*/

Shuttle Sort - Simple Insertion Sort

#include< stdio.h>
#include< conio.h>

void shutsort(int a[],int n)
{
int j,i=1,mid;

while(i< n)
{
j=i-1;
while(j>=0)
{
if(a[j]>a[j+1])
{
mid = a[j];
a[j] = a[j+1];
a[j+1]=mid;
j--;
}
else
break;
}
i++;
}
}

main()
{
int a[10],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
shutsort(a,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT
Enter The number Of Elements : 5

Element 1 : 21

Element 2 : 36

Element 3 : 54

Element 4 : 98

Element 5 : 1

Array Befor Sorting : 21 36 54 98 1
Array After Sorting : 1 21 36 54 98
*/

Shell Sort

#include< stdio.h>
#include< conio.h>

void shellsort(int a[],int n)
{
int j,i,k,m,mid;
for(m = n/2;m>0;m/=2)
{
for(j = m;j< n;j++)
{
for(i=j-m;i>=0;i-=m)
{
if(a[i+m]>=a[i])
break;
else
{
mid = a[i];
a[i] = a[i+m];
a[i+m] = mid;
}
}
}
}
}

main()
{
int a[10],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
shellsort(a,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT

Enter The number Of Elements : 5

Element 1 : 21

Element 2 : 36

Element 3 : 54

Element 4 : 2

Element 5 : 0

Array Befor Sorting : 21 36 54 2 0
Array After Sorting : 0 2 21 36 54
*/

Merge Sort

#include< stdio.h>
#include< conio.h>

void mergesort(int a[],int n)
{
int b[50],c,low1,high1,high2,low2;
int i,k,j;
c=1;
while(c< n)
{
low1=0;
k=0;
while(low1+c< n)
{
low2=low1+c ;
high1=low2-1;
if(low2+c-1< n)
high2=low2+c-1;
else
high2=n-1;
i=low1;
j=low2;
while(i< =high1 && j< =high2)
{
if(a[i]< =a[j])
b[k++] =a[i++];
else
b[k++] = a[j++];

}
while(i< =high1)
b[k++]=a[i++];
while(j< =high2)
b[k++] =a[j++];
low1=high2+1;
}
i=low1;
while(k< n)
b[k++] =a[i++];
for(i=0;i< n;i++)
a[i]=b[i];
c=c*2;
}
}

main()
{
int a[20],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
mergesort(a,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT

Enter The number Of Elements : 10

Element 1 : 12

Element 2 : 54

Element 3 : 98

Element 4 : 6566

Element 5 : 45

Element 6 : 12

Element 7 : 5

Element 8 : 1

Element 9 : 156

Element 10 : 21

Array Befor Sorting : 12 54 98 6566 45 12 5 1 156 21
Array After Sorting : 1 5 12 12 21 45 54 98 156 6566


*/

Quicksort

#include< stdio.h>
#include< conio.h>

void quicksort(int [],int,int);
int partition(int [],int,int);


main()
{
int a[20],p,q,i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

p=0;
q=n-1;
printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
quicksort(a,p,q);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}


void quicksort(int a[],int p,int q)
{
int j;
if(p< q)
{
j=partition(a,p,q+1);
quicksort(a,p,j-1);
quicksort(a,j+1,q);
}
}

int partition(int a[],int m,int p)
{
int v,i,j;
int temp;
v=a[m];
i=m;j=p;
do
{
do
{
i += 1;
}
while(a[i]< v);
do
{
j -= 1;
}
while(a[j]>v);

if(i< j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
while(i< j);
a[m] =a[j];
a[j] = v;
return j;
}

/* OUTPUT

Enter The number Of Elements : 10

Element 1 : 12

Element 2 : 54

Element 3 : 98

Element 4 : 6566

Element 5 : 45

Element 6 : 12

Element 7 : 5

Element 8 : 1

Element 9 : 156

Element 10 : 21

Array Befor Sorting : 12 54 98 6566 45 12 5 1 156 21
Array After Sorting : 1 5 12 12 21 45 54 98 156 6566


*/

Simple Selection Sort

#include< stdio.h>
#include< conio.h>

void simplesel(int a[],int b[],int n)
{
int j,i=0,k,H;
int L=32760;
k=0;
L=H;
while(i< n)
{
for(j=0;j< n;j++)
{
if(a[j]< L)
{
L = a[j];
k = j;
}
}
a[k] = H;
b[i] = L;
L = H;
i++;
}
}

main()
{
int a[10],b[10],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
simplesel(a,b,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",b[i]);
getch();
return 0;
}
/* OUTPUT
Enter The number Of Elements : 10

Element 1 : 21

Element 2 : 25

Element 3 : 63

Element 4 : 45

Element 5 : 1

Element 6 : 147

Element 7 : 10

Element 8 : 78

Element 9 : 96

Element 10 : 5
Array Befor Sorting : 21 25 63 45 1 147 10 78 96 5
Array After Sorting : 1 5 10 21 25 45 63 78 96 147
*/

Binary Tree Sort

This has two phases. First phase is creating a binary search tree using the given array elements. Second phase is traverse the given binary search tree in inorder, thus resulting in a sorted array.

Performance
The average number of comparisons for this method is O(nlog₂n)
But in the worst case, the number of comparisons are reduced by O(n²), a case which arises when the sort tree is severely unbalanced .


/****** C Program For Implementation Of Binary Sort ***/

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *rightchild;
int data;
struct btreenode *leftchild;
};

insert(struct btreenode **sr,int num)
{
if(*sr==NULL)
{
*sr=malloc(sizeof(struct btreenode));

(*sr)- >leftchild=NULL;
(*sr)- >data=num;
(*sr)- >rightchild=NULL;
return;
}
else
{
if(num< (*sr)- >data)
insert(&((*sr)- >leftchild),num);
else
insert(&((*sr)- >rightchild),num);
}
return;
}

inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr- >leftchild);
printf("%d ",sr- >data);
inorder(sr- >rightchild);
}
else
return;
}

postorder(struct btreenode *sr)
{
if(sr!=NULL)
{
postorder(sr- >rightchild);
printf("%d ",sr- >data);
postorder(sr- >leftchild);
}
else
return;
}

void main()
{
struct btreenode *bt;
int req,i=0,num,a[10],no;

bt=NULL;
clrscr();

while(i < 5)
{
printf("\nEnter value to be inserted: ");
scanf("%d",&a[i]);
insert(&bt,a[i]);
i++;
}
clrscr();
printf("\n\nSorted Binary tree in ascending order== > \n\n");
inorder(bt);
printf("\n\nSortred binary tree in descending order== >\n\n");
postorder(bt);
getch();
}


/************************** OUTPUT ***********************

Enter value to be inserted: 9

Enter value to be inserted: 8

Enter value to be inserted: 4

Enter value to be inserted: 5

Enter value to be inserted: 7


Sorted Binary tree in ascending order== >

4 5 7 8 9

Sortred binary tree in descending order== >

9 8 7 5 4 */

Straight Selection Sort

One of the easiest sorting methods is selection sort. Beginning with the first element of the given array, a search is made to find the largest element in the array. When the element is found this element is interchanged with the last element of the array. Now the size of the unsorted array will be reduced but one. A search for the largest element of the unsorted array is carried out. When this element is found it will be interchanged with the last element of the unsorted array. Once again the unsorted array will be reduced by 1 and the above process will be repeated till the entire array is sorted in ascending order.

ALGORITHM
1. Establish an array ‘a’ with ‘n’ elements
2. Repeat through step 6 for ‘n-1’ times
3. Repeat the position of the array already sorted
4. Repeat step 5 for the elements in unsorted position of the array
5. Record location of the largest element in the unsorted array
6. Exchange last element in the unsorted array with the largest element

PERFORMANCE OF THE ALGORITHM
During the first pass, in which the largest element is found, n-1 elements are compared. In general, for ith pass of the sort, n-I comparisons are required

So total number of comparisons
n-1 + n-2 + ……… + 1

Time Complexity = O(n²)

/**** C Program For Implementation Of Selection Sort ****/

#define MAX 10
char name[MAX][15];
void sort(int n)
{
int i,j,index;
char temp[15];
for(i=n;i >0;i--)
{
strcpy(temp,name[1]);
index=1;
for(j=1;j< =i;j++) { if(strcmp(name[j],temp) >0)
{
strcpy(temp,name[j]);
index=j;
}
}
strcpy(name[index],name[i]);
strcpy(name[i],temp);
}
}
void main()
{
int i,j,n;
clrscr();
A: printf("\n\nENTER HOW MANY NAMES: ");
scanf("%d",&n);
if(n >MAX)
{
printf("\n\t\tARRAY SIZE IS ONLY %d",MAX);
goto A;
}
else
{
printf("\n\t ENTER %d Names : \n",n);
for(i=1;i< =n;i++) { printf("\t\t"); scanf("%s",name[i]); } sort(n); printf("\n\n\t\t*********** SORTED LIST ************"); for(i=1;i< =n;i++) printf("\n \t\t\t\t%s",name[i]); } getch(); } /********** OUTPUT ************** ENTER HOW MANY NAMES: 12 ARRAY SIZE IS ONLY 10 ENTER HOW MANY NAMES: 4 ENTER 4 Names : Lionel Cyril Valerian Noronha *********** SORTED LIST ************ Cyril Lionel Noronha Valerian **************************************/

Merge Sort

Merging is the process of combining two or more sorted arrays into a third sorted array. We can use this technique to sort an array of n elements as follows.
Divide the array into ‘n’ sub arrays of size 1 and merge adjacent pairs of sub arrays. Then we can have approximately n/2 sorted sub arrays of size 2. Repeat this process until there is 1 array containing n elements.
Algorithm
1. Establish a sub array ‘a’ with n elements
2. Let size < - 1 3. Repeat steps 4 through 6 until size >= n
4. Subdivide the sub array into sub arrays of size ‘size’
5. Merge adjacent pairs of sub arrays
6. Double the size

/*** C Program For Implementation Of Merge Sort ***/

#define MAX 20

void mergesort(int *,int);
void main()
{
int x[MAX],n,j,i;
char ans;
clrscr();
{
printf("\nEnter The Length Of The Array\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("Enter Element %d\t: ",i+1);
scanf("%d",&x[i]);
}
mergesort(x,n);
printf("\n\t│ Sorted Array :\t\t\t│\n\t│");
for(i=0;i< n;i++)
printf("%d\t",x[i]);
}
printf("│");
getch();
}

void mergesort(int x[],int n)
{
int sub[MAX];
int i,j,k,list1,list2,u1,u2,size=1;
while(size< n)
{
list1=0;
k=0;

while((list1+size)< n)
{
list2=list1+size;
u1=list2-1;
u2=((list2+size-1)< n)?(list2+size-1):(n-1);

for(i=list1,j=list2;i< =u1 &&amp;amp;amp; j< =u2;k++)
if(x[i]< =x[j])
sub[k]=x[i++];
else
sub[k]=x[j++];

for(;i< =u1;k++)
sub[k]=x[i++];

for(;j< =u2;k++)
sub[k]=x[j++];

list1=u2+1;
}
for(i=list1;k< n;i++)
sub[k++] = x[i];
for(i=0;i< n;i++)
x[i] =sub[i];
size *= 2;
}
}
/********* OUTPUT **********

Enter The Length Of The Array : 5
Enter Element 1 : 12
Enter Element 2 : 69
Enter Element 3 : 78
Enter Element 4 : 2
Enter Element 5 : 5

│ Sorted Array : │
│2 5 12 69 78 │
*/

Circular Queue

A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don't have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.

Algorithm for Insertion:-
Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4:

1. if the "front" points where "rear" is pointing and the queue holds a not NULL value for it, then its a "queue overflow" state, so quit; else go to step-4.2
2. insert the new value for the queue position pointed by the "rear"

Algorithm for deletion:-
Step-1: If the queue is empty then say "empty queue" and quit; else continue
Step-2: Delete the "front" element
Step-3: If the "front" is pointing to the last position of the queue then step-4 else step-5
Step-4: Make the "front" point to the first position in the queue and quit
Step-5: Increment the "front" position by one


/****** C Program For Impelmetation Of Circular Queue *******/
#define MAX 5

struct queue
{
int arr[MAX];
int rear,front;
};

int isempty(struct queue *p)
{
if(p->front ==p->rear)
return 1;
else
return 0;
}

void insertq(struct queue *p,int v)
{
int t;
t = (p->rear+1)%MAX;
if(t == p->front)
printf("\nQueue Overflow\n");
else
{
p->rear=t;
p->arr[p->rear]=v;
}
}
int removeq(struct queue *p)
{
if(isempty(p))
{
printf("\nQueue Underflow");
exit(0);
}
else
{
p->front=(p->front + 1)%MAX;
return(p->arr[p->front]);
}
}

void main()
{
struct queue q;
char ch;
int no;
clrscr();
q.rear=q.front =0;
insertq(&q,7);
insertq(&q,10);
insertq(&q,12);
insertq(&q,15);
insertq(&q,8);
printf("\n%d\n",removeq(&q));
printf("%d\n",removeq(&q));
printf("%d\n",removeq(&q));
printf("%d\n",removeq(&q));
removeq(&q);
getch();
}
/************** OUTPUT ****************

Queue Overflow

7
10
12
15

Queue Underflow */

Queue

A queue is a buffer abstract data structure providing services in computer science, transport and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. The most well known operation of the queue is the First-In-First-Out (FIFO) queue process. In a FIFO queue, the first element in the queue will be the first one out; this is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked. Unless otherwise specified, the remainder of the article will refer to FIFO queues. There are also non-FIFO queue data structures, like priority queues.

/******** C Program For Impelmetation Of Queue ***********/

#define MAXSIZE 10

struct st
{
int front,rear;
int queue[MAXSIZE];
};

struct st s;

int empty(void);
int full(void);
void add(void);
void delete(void);
void display(void);

void main()
{
char ans;
int ch;
s.front = 0;
s.rear = 0;

do
{
clrscr();
printf("********Queue Program**********\n");
printf("1. ADD\n");
printf("2. DELETE\n");
printf("3. DISPLAY\n");
printf("4. QUIT\n");
printf("Enter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
add();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
break;

default:
printf("INVALID CHOICE!!!!!!!!!!!!!!!!\n");
break;
}
printf("\nWant To Go To The Main Menu[y/n]");
flushall();
ans = getch();
}
while(ans == 'y' ans == 'Y');
printf("\nPress Any Key To Continue\n");
getch();
}

int full(void)
{
if (s.rear == MAXSIZE)
return(1);
else
return(0);
}
int empty(void)
{
if (s.front == s.rear + 1)
return(1);
else
return(0);
}

void add(void)
{
char ch;
int x;
do
{
if(full() == 1)
{
printf("\n\nQueue Full\n");
break;
}
else
{
s.rear = s.rear + 1;
printf("\nEnter An Element to Be Added ");
scanf("%d",&x);
s.queue[s.rear] = x;
if(s.rear == 1) s.front ++;
}
printf("\nDo You Want to Add More Elements[y/n]:");
flushall();
ch = getch();
}
while(ch=='y' ch == 'Y');
}

void delete(void)
{
char ch;
do
{
if(empty() == 1)
{
printf("\n\nQueue Empty\n");
break;
}
else
{
printf("% d Has Been Deleted!",s.queue[s.front]);
s.front = s.front +1;
}
printf("\nWant to Delete More [y\n]");
flushall();
ch = getch();
}
while(ch=='y' ch == 'Y');
}

void display(void)
{
int i;
clrscr();
if(empty () == 1)
printf("\nQueue Empty!!");
else
{
printf("\nDisplaying Queue\n");
for(i = s.front;i printf("%d\n",s.queue[i]);
}
}
/************ OUTPUT ***************

**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 1

Enter An Element to Be Added 1
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 2
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 3
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 4
Do You Want to Add More Elements[y/n]:y
Enter An Element to Be Added 5
Do You Want to Add More Elements[y/n]:n
Want To Go To The Main Menu[y\n] y

**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 3

Displaying Queue
1
2
3
4
5
Want To Go To The Main Menu[y\n] y

**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 2
1 Has Been Deleted!!
Do You Want To Delete More?[y/n] n
Want to Go To Main Menue[y/n] y

**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 3

Displaying Queue
2
3
4
5
Want To Go To The Main Menu[y\n] y

**********Queue Program**********
1. ADD
2. DELETE
3. DISPLAY
4. QUIT
Enter Your Choice : 4 */

Stack

One way to think about this implementation is to think of functions as being stacked on top of each other; the last one added to the stack is the first one taken off. In this way, the data structure itself enforces the proper order of calls. Conceptually, a stack is simple: a data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack; the only element that can be removed is the element that was at the top of the stack.

Consequently, a stack is said to have "first in last out" behavior (or "last in, first out"). The first item added to a stack will be the last item removed from a stack. So what's the big deal? Where do stacks come into play? As you've already seen, stacks are a useful way to organize our thoughts about how functions are called. In fact, the "call stack" is the term used for the list of functions either executing or watiing for other functions to return. In a sense, stacks are part of the fundamental language of computer science. When you want to express an idea of the "first in last out" variety, it just makes sense to talk about it using the common terminology. Moreover, such operations show up an awful lot, from theoretical computer science tools such as a push-down automaton to AI, including implementations of depth-first search.

Stacks have some useful terminology associated with them:

1. Push To add an element to the stack
2. Pop To remove an element from the stock
3. Peek To look at elements in the stack without removing them
4. LIFO Refers to the last in, first out behavior of the stack
5. FILO Equivalent to LIFO

General Algorithm

1. [Prologue] Save the parameters, Local Variables and return address.
2. [Body] If the base criterion has been reached, then perform the final computation and go to step 3; otherwise, perfprm the partial computation and go to step 1(initialize a recursive call)
3. [Epilogue] Restore the most recently saved parameters, local variables, and return address. Go to this return address.

/**************** C Program For Impelmetation Of Stack ********************/

#define MAXSIZE 10

struct st
{
int top;
int stack[MAXSIZE];
};

struct st s;

int empty(void);
int full(void);
void push(void);
void pop(void);
void display(void);

void main()
{
char ans;
int ch;
do
{
clrscr();
printf("********Stack Program**********\n");
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.DISPLAY\n");
printf("4.QUIT\n");
printf("Enter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
break;

default:
printf("INVALID CHOICE!!!!!!!!!!!!!!!!\n");
break;
}
printf("Want To Go To The Main Menu[y/n]");
flushall();
ans = getch();
}
while(ans == 'y' ans == 'Y');
printf("\nPress Any Key To Exit");
getch();
}

int full(void)
{
if (s.top == MAXSIZE)
return(1);
else
return(0);
}

int empty(void)
{
if (s.top == 0)
return(1);
else
return(0);
}
void push(void)
{
char ch;
int x;
do
{
if(full() == 1)
{
printf("\nStack Full\n");
break;
}
else
{
s.top = s.top + 1;
printf("\nEnter An Element To Be Pushed: ");
scanf("%d",&x);
s.stack[s.top] = x;
}
printf("\nDo You Want To Push More Elements[y/n]");
flushall();
ch = getch();
}
while(ch == 'y' ch == 'Y');
}

void pop(void)
{
char ch;
do
{
if(empty() == 1)
{
printf("\nStack Empty\n");
break;
}
else
{
printf("\n%d has been popped !",s.stack[s.top]);
s.top = s.top - 1;
}
printf("\nDo you Want To Pop Out More?[y/n]");
flushall();
ch = getch();
}
while(ch == 'Y' ch == 'y');
}

void display(void)
{
int i;
clrscr();
if(empty() == 1)
printf("\nStack Empty!!!");
else
{
printf("Displaying Stack............\n");
for(i = s.top; i>0;i--)
printf("%d",s.stack[i]);
}
}
/************** OUTPUT *************

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 1

Enter An Element To Be Pushed : 1
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 2
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 3
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 4
Do YOu Want To Push More Elements [y\n] y
Enter An Element To Be Pushed : 5
Do YOu Want To Push More Elements [y\n] n
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 3

Displaying Stack......
5
4
3
2
1
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 2

5 Has Been Popped!
Do You Want To Pop More? [y\n] y
4 Has Been Popped!

Do You Want To Pop More? [y\n] n
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 3

Displaying Stack.........
3
2
1
Want To Go Main Menu? [y\n] y

********Stack Program**********
1. PUSH
2. POP
3. DISPLAY
4. QUIT
Enter Your Choice : 4 */