The Below Program performs Sorting of Following type 1)Merge Sort 2)Heap Sort 3)Radix Sort and 4)Quick Sort. The program is a part of Mumbai University MCA Colleges Data Structure C program MCA Sem 2
Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 30
void radix_sort();
void display1();
void del_root(int last);
void disp();
void heap_sort();
void create_heap();
void insert(int num,int loc);
void sort(int arr[],int low,int up);
void display(int arr[],int low,int up);
enum bool { FALSE,TRUE };
void Merge();
void Quick();
void Heap();
void Radix();
struct node
{
int info ;
struct node *link;
}*start=NULL;
int i,j,k,n,a[50],temp,choice,size,l1,h1,l2,h2,arr[50];
void main()
{
clrscr();
while(1)
{
printf("\n\n------------------------------- MENU FOR SORTING -------------------------------\n\n");
printf("1.Merge Sort\n\n2.Quick Sort\n\n3.Heap Sort\n\n4.Radix Sort\n\n5.Exit\n\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
Merge();
break;
case 2:
Quick();
break;
case 3:
Heap();
break;
case 4:
Radix();
break;
case 5:
exit(1);
default:
printf("\n\nInvalid Choice!!!!!!Try Again");
}
getch();
}
}
void Merge()
{
int arr[MAX],temp[MAX];
printf("\n\n---------------------------------- MERGE SORT --------------------------------\n");
printf("\nEnter the size of the array : ");
scanf("%d",&n);
printf("\nEnter %d elements : ",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\n\n------------------------------- Original Array ----------------------------\n\n ");
for( i = 0 ; i<n ; i++)
printf("%d\t ", arr[i]);
printf("\n\n----------------------------------------------------------------------------\n\n ");
for(size=1; size < n; size=size*2 )
{
l1=0;
k=0;
while( l1+size < n)
{
h1=l1+size-1;
l2=h1+1;
h2=l2+size-1;
if( h2>=n )
h2=n-1;
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++];
l1=h2+1;
}
for(i=l1; k<n; i++)
temp[k++]=arr[i];
for(i=0;i<n;i++)
arr[i]=temp[i];
printf("\n\nSize= %d\n------------------------------- Elements are -------------------------------\n\n",size);
for( i = 0 ; i<n ; i++)
printf("%d\t ", arr[i]);
}
printf("\n\n--------------------------------- Sorted Array -----------------------------------\n\n");
for( i = 0 ; i<n ; i++)
printf("%d\t ", arr[i]);
printf("\n");
getch();
}
void Quick()
{
int array[MAX];
printf("\n\n------------------------- QUICK SORT --------------------------------\n");
printf("\n\nEnter the size of array : ");
scanf("%d",&n);
printf("\n\nEnter %d elements : ",n);
for(i=0;i<n;i++)
{
scanf("%d",&array[i]);
}
printf("\n\n------------------------------- Unsorted Array -------------------------\n\n");
display(array,0,n-1);
printf("\n");
sort(array,0,n-1);
printf("\n\n---------------------------------- Sorted Array -----------------------\n\n");
display(array,0,n-1);
printf("\n");
getch();
}
void sort(int arr[],int low,int up)
{
int piv,left,right;
enum bool pivot_placed=FALSE;
left=low;
right=up;
piv=low;
if(low>=up)
return;
printf("\n\n------------------------------ Sublist -----------------------------\n");
display(arr,low,up);
while(pivot_placed==FALSE)
{
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;
}
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;
}
}
printf("\n\n-------------------------------- Pivot Placed is %d -----------------------------\n",arr[piv]);
display(arr,low,up);
printf("\n");
sort(arr,low,piv-1);
sort(arr,piv+1,up);
}
void display(int arr[],int low,int up)
{
int i;
printf("\n\n");
for(i=low;i<=up;i++)
printf("%d \t",arr[i]);
}
void Heap()
{
printf("\n\n----------------------- HEAP SORT -------------\n\n");
printf("Enter number of elements : ");
scanf("%d",&n);
printf("\n\nEnter %d element : ",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\n\n---------------------- Original list ---------------------------\n\n");
disp();
create_heap();
printf("\n\n-------------------------- Heap -------------------------------------------\n\n");
disp();
heap_sort();
printf("\n\n--------------------------------- Sorted list ---------------------------\n\n");
disp();
return;
}
void disp()
{
printf("\n");
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
}
void create_heap()
{
int i;
for(i=0;i<n;i++)
insert(arr[i],i);
}
void 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;
}
arr[0]=num;
}
void heap_sort()
{
int last;
for(last=n-1; last>0; last--)
del_root(last);
}
void del_root(int last)
{
int left,right;
i=0;
temp=arr[i];
arr[i]=arr[last];
arr[last]=temp;
left=2*i+1;
right=2*i+2;
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;
}
if( left==last-1 && arr[i]<arr[left] )
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
}
}
void Radix()
{
struct node *tmp,*q;
int item;
printf("\n\n----------------------- RADIX SORT -------------\n\n");
printf("Enter the number of elements in the list : ");
scanf("%d", &n);
printf("\nEnter %d element : ",n);
for(i=0;i<n;i++)
{
scanf("%d",&item);
tmp= malloc(sizeof(struct node));
tmp->info=item;
tmp->link=NULL;
if(start==NULL)
start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}
printf("\n\n------------------------- ORIGINAL ARRAY ---------------------\n\n");
display1();
radix_sort();
printf("\n\n---------------------------------- SORTED ARRAY --------------------\n\n");
display1();
}
void display1()
{
struct node *p=start;
printf("\n");
while( p !=NULL)
{
printf("%d\t ", p->info);
p= p->link;
}
}
void radix_sort()
{
int 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("\n\nPASS %d :\t 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)
{
dig = digit(p->info, k);
if(dig>maxdig)
maxdig=dig;
if(dig<mindig)
mindig=dig;
if(front[dig] == NULL)
front[dig] = p ;
else
rear[dig]->link = p ;
rear[dig] = p ;
p=p->link;
}
printf("\n\nmindig=%d \t maxdig=%d",mindig,maxdig);
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("\n\n------------ New list ---------------------\n\n ");
display1();
}
}
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("\n\nLargest Element is %d : \n",large);
while(large != 0)
{
ndig++;
large = large/10 ;
}
printf("\n\nNumber of digits in it are %d\n",ndig);
return(ndig);
}
int digit(int number, int k)
{
int digit, i ;
for(i = 1 ; i <=k ; i++)
{
digit = number % 10 ;
number = number /10 ;
}
return(digit);
}Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.
Download
:)
ReplyDelete