data strutcher programming

/*Program of sorting using address calculation sort*/
computer science tutorial
seminar topic
newidea
#include<stdio.h>
#include<malloc.h>
#define MAX 20

struct node
{
int info ;
struct node *link;
};
struct node *head[10];
int n,i,arr[MAX];
main()
{

int i;
printf("Enter the number of elements in the list : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}/*End of for */

printf("Unsorted list is :\n");
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
addr_sort();
printf("Sorted list is :\n");
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}/*End of main()*/

addr_sort()
{
int i,k,dig;
struct node *p;
int addr;
k=large_dig();
for(i=0;i<=9;i++)
head[i]=NULL;
for(i=0;i<n;i++)
{
addr=hash_fn( arr[i],k );
insert(arr[i],addr);
}

for(i=0; i<=9 ; i++)
{
printf("head(%d) -> ",i);
p=head[i];
while(p!=NULL)
{
printf("%d ",p->info);
p=p->link;
}
printf("\n");
}

/*Taking the elements of linked lists in array*/
i=0;
for(k=0;k<=9;k++)
{
p=head[k];
while(p!=NULL)
{
arr[i++]=p->info;
p=p->link;
}
}
}/*End of addr_sort()*/

/*Inserts the number in sorted linked list*/
insert(int num,int addr)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;
/*list empty or item to be added in begining */
if(head[addr] == NULL || num < head[addr]->info)
{
tmp->link=head[addr];
head[addr]=tmp;
return;
}
else
{
q=head[addr];
while(q->link != NULL && q->link->info < num)
q=q->link;
tmp->link=q->link;
q->link=tmp;
}
}/*End of insert()*/

/* Finds number of digits in the largest element of the list */
int large_dig()
{

int large = 0,ndig = 0 ;

for(i=0;i<n;i++)
{
if(arr[i] > large)
large = arr[i];
}
printf("Largest Element is %d , ",large);
while(large != 0)
{
ndig++;
large = large/10 ;
}

printf("Number of digits in it are %d\n",ndig);
return(ndig);
} /*End of large_dig()*/

hash_fn(int number,int k)
{
/*Find kth digit of the number*/
int digit,addr,i;
for(i = 1 ; i <=k ; i++)
{
digit = number % 10 ;
number = number /10 ;
}
addr=digit;
return(addr);
}/*End of hash_fn()*/

/* Program of sorting using bubble sort */
#include <stdio.h>
#define MAX 20
main()
{
int arr[MAX],i,j,k,temp,n,xchanges;
printf("Enter the number of elements : ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
/* Bubble sort*/

for (i = 0; i < n-1 ; i++)
{
xchanges=0;
for (j = 0; j <n-1-i; j++)
{
if (arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
xchanges++;
}/*End of if*/
}/*End of inner for loop*/
if(xchanges==0) /*If list is sorted*/
break;
printf("After Pass %d elements are : ",i+1);
for (k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
}/*End of outer for loop*/

printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/

/* Program of sorting through heapsort*/
# include <stdio.h>

int arr[20],n;

main()
{
int i;
printf("Enter number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Entered list is :\n");
display();

create_heap();

printf("Heap is :\n");
display();

heap_sort();
printf("Sorted list is :\n");
display();
}/*End of main()*/

display()
{ int i;
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}/*End of display()*/

create_heap()
{
int i;
for(i=0;i<n;i++)
insert(arr[i],i);
}/*End of create_heap()*/

insert(int num,int loc)
{
int par;
while(loc>0)
{
par=(loc-1)/2;
if(num<=arr[par])
{
arr[loc]=num;
return;
}
arr[loc]=arr[par];
loc=par;
}/*End of while*/
arr[0]=num;
}/*End of insert()*/


heap_sort()
{
int last;
for(last=n-1; last>0; last--)
del_root(last);
}/*End of del_root*/

del_root(int last)
{
int left,right,i,temp;
i=0; /*Since every time we have to replace root with last*/
/*Exchange last element with the root */
temp=arr[i];
arr[i]=arr[last];
arr[last]=temp;

left=2*i+1; /*left child of root*/
right=2*i+2;/*right child of root*/

while( right < last)
{
if( arr[i]>=arr[left] && arr[i]>=arr[right] )
return;
if( arr[right]<=arr[left] )
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
i=left;
}
else
{
temp=arr[i];
arr[i]=arr[right];
arr[right]=temp;
i=right;
}
left=2*i+1;
right=2*i+2;
}/*End of while*/
if( left==last-1 && arr[i]<arr[left] )/*right==last*/
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
}
}/*End of del_root*/

/* Program of sorting using insertion sort */
#include <stdio.h>
#define MAX 20

main()
{
int arr[MAX],i,j,k,n;
printf("Enter the number of elements : ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d", &arr[i]);
}
printf("Unsorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
/*Insertion sort*/
for(j=1;j<n;j++)
{
k=arr[j]; /*k is to be inserted at proper place*/
for(i=j-1;i>=0 && k<arr[i];i--)
arr[i+1]=arr[i];
arr[i+1]=k;
printf("Pass %d, Element inserted in proper place: %d\n",j,k);
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/

/* Program of merging two sorted arrays into a third sorted array*/
#include<stdio.h>

main()
{
int arr1[20],arr2[20],arr3[40];
int i,j,k;
int max1,max2;

printf("Enter the number of elements in list1 : ");
scanf("%d",&max1);
printf("Take the elements in sorted order :\n");
for(i=0;i<max1;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr1[i]);
}
printf("Enter the number of elements in list2 : ");
scanf("%d",&max2);
printf("Take the elements in sorted order :\n");
for(i=0;i<max2;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr2[i]);
}
/* Merging */
i=0; /*Index for first array*/
j=0; /*Index for second array*/
k=0; /*Index for merged array*/

while( (i < max1) && (j < max2) )
{
if( arr1[i] < arr2[j] )
arr3[k++]=arr1[i++];
else
arr3[k++]=arr2[j++];
}/*End of while*/
/*Put remaining elements of arr1 into arr3*/
while( i < max1 )
arr3[k++]=arr1[i++];
/*Put remaining elements of arr2 into arr3*/
while( j < max2 )
arr3[k++]=arr2[j++];

/*Merging completed*/
printf("List 1 : ");
for(i=0;i<max1;i++)
printf("%d ",arr1[i]);
printf("\nList 2 : ");
for(i=0;i<max2;i++)
printf("%d ",arr2[i]);
printf("\nMerged list : ");
for(i=0;i<max1+max2;i++)
printf("%d ",arr3[i]);
printf("\n");
}/*End of main()*/

/*Program of sorting using quick sort through recursion*/
#include<stdio.h>
#define MAX 30

enum bool { FALSE,TRUE };
main()
{
int array[MAX],n,i;
printf("Enter the number of elements : ");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&array[i]);
}

printf("Unsorted list is :\n");
display(array,0,n-1);
printf("\n");

quick(array,0,n-1);

printf("Sorted list is :\n");
display(array,0,n-1);
printf("\n");

}/*End of main() */

quick(int arr[],int low,int up)
{
int piv,temp,left,right;
enum bool pivot_placed=FALSE;
left=low;
right=up;
piv=low; /*Take the first element of sublist as piv */

if(low>=up)
return;
printf("Sublist : ");
display(arr,low,up);

/*Loop till pivot is placed at proper place in the sublist*/
while(pivot_placed==FALSE)
{
/*Compare from right to left */
while( arr[piv]<=arr[right] && piv!=right )
right=right-1;
if( piv==right )
pivot_placed=TRUE;
if( arr[piv] > arr[right] )
{
temp=arr[piv];
arr[piv]=arr[right];
arr[right]=temp;
piv=right;
}
/*Compare from left to right */
while( arr[piv]>=arr[left] && left!=piv )
left=left+1;
if(piv==left)
pivot_placed=TRUE;
if( arr[piv] < arr[left] )
{
temp=arr[piv];
arr[piv]=arr[left];
arr[left]=temp;
piv=left;
}
}/*End of while */

printf("-> Pivot Placed is %d -> ",arr[piv]);
display(arr,low,up);
printf("\n");

quick(arr,low,piv-1);
quick(arr,piv+1,up);
}/*End of quick()*/
display(int arr[],int low,int up)
{
int i;
for(i=low;i<=up;i++)
printf("%d ",arr[i]);
}

/*Program of sorting using radix sort*/
# include<stdio.h>
# include<malloc.h>

struct node
{
int info ;
struct node *link;
}*start=NULL;

main()
{
struct node *tmp,*q;
int i,n,item;

printf("Enter the number of elements in the list : ");
scanf("%d", &n);

for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&item);

/* Inserting elements in the linked list */
tmp= malloc(sizeof(struct node));
tmp->info=item;
tmp->link=NULL;

if(start==NULL) /* Inserting first element */
start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}/*End of for*/

printf("Unsorted list is :\n");
display();
radix_sort();
printf("Sorted list is :\n");
display ();
}/*End of main()*/

display()
{
struct node *p=start;
while( p !=NULL)
{
printf("%d ", p->info);
p= p->link;
}
printf("\n");
}/*End of display()*/

radix_sort()
{
int i,k,dig,maxdig,mindig,least_sig,most_sig;
struct node *p, *rear[10], *front[10];

least_sig=1;
most_sig=large_dig(start);

for(k = least_sig; k <= most_sig ; k++)
{
printf("PASS %d : Examining %dth digit from right ",k,k);
for(i = 0 ; i <= 9 ; i++)
{
rear[i] = NULL;
front[i] = NULL ;
}
maxdig=0;
mindig=9;
p = start ;
while( p != NULL)
{
/*Find kth digit in the number*/
dig = digit(p->info, k);
if(dig>maxdig)
maxdig=dig;
if(dig<mindig)
mindig=dig;

/*Add the number to queue of dig*/
if(front[dig] == NULL)
front[dig] = p ;
else
rear[dig]->link = p ;
rear[dig] = p ;
p=p->link;/*Go to next number in the list*/
}/*End while */
/* maxdig and mindig are the maximum amd minimum
digits of the kth digits of all the numbers*/
printf("mindig=%d maxdig=%d\n",mindig,maxdig);
/*Join all the queues to form the new linked list*/
start=front[mindig];
for(i=mindig;i<maxdig;i++)
{
if(rear[i+1]!=NULL)
rear[i]->link=front[i+1];
else
rear[i+1]=rear[i];
}
rear[maxdig]->link=NULL;
printf("New list : ");
display();
}/* End for */

}/*End of radix_sort*/

/* This function finds number of digits in the largest element of the list */
int large_dig()
{
struct node *p=start ;
int large = 0,ndig = 0 ;

while(p != NULL)
{
if(p ->info > large)
large = p->info;
p = p->link ;
}
printf("Largest Element is %d , ",large);
while(large != 0)
{
ndig++;
large = large/10 ;
}

printf("Number of digits in it are %d\n",ndig);
return(ndig);
} /*End of large_dig()*/

/*This function returns kth digit of a number*/
int digit(int number, int k)
{
int digit, i ;
for(i = 1 ; i <=k ; i++)
{
digit = number % 10 ;
number = number /10 ;
}
return(digit);
}/*End of digit()*/

/*Program of sorting using selection sort*/
#include <stdio.h>
#define MAX 20

main()
{
int arr[MAX], i,j,k,n,temp,smallest;
printf("Enter the number of elements : ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d", &arr[i]);
}
printf("Unsorted list is : \n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
/*Selection sort*/
for(i = 0; i< n - 1 ; i++)
{
/*Find the smallest element*/
smallest = i;
for(k = i + 1; k < n ; k++)
{
if(arr[smallest] > arr[k])
smallest = k ;
}
if( i != smallest )
{
temp = arr [i];
arr[i] = arr[smallest];
arr[smallest] = temp ;
}
printf("After Pass %d elements are : ",i+1);
for (j = 0; j < n; j++)
printf("%d ", arr[j]);
printf("\n");
}/*End of for*/
printf("Sorted list is : \n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/

/* Program of sorting using merge sort without recursion*/
#include<stdio.h>
#define MAX 30

main()
{
int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;

printf("Enter the number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted list is : ");
for( i = 0 ; i<n ; i++)
printf("%d ", arr[i]);

/*l1 lower bound of first pair and so on*/
for(size=1; size < n; size=size*2 )
{
l1=0;
k=0; /*Index for temp array*/
while( l1+size < n)
{
h1=l1+size-1;
l2=h1+1;
h2=l2+size-1;
if( h2>=n ) /* h2 exceeds the limlt of arr */
h2=n-1;
/*Merge the two pairs with lower limits l1 and l2*/
i=l1;
j=l2;
while(i<=h1 && j<=h2 )
{
if( arr[i] <= arr[j] )
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=h1)
temp[k++]=arr[i++];
while(j<=h2)
temp[k++]=arr[j++];
/**Merging completed**/
l1=h2+1; /*Take the next two pairs for merging */
}/*End of while*/

for(i=l1; k<n; i++) /*any pair left */
temp[k++]=arr[i];

for(i=0;i<n;i++)
arr[i]=temp[i];

printf("\nSize=%d \nElements are : ",size);
for( i = 0 ; i<n ; i++)
printf("%d ", arr[i]);
}/*End of for loop */
printf("Sorted list is :\n");
for( i = 0 ; i<n ; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/