Pages

Data Structure Sorting C program

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

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 30

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();

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

int i,j,k,n,a[50],temp,choice,size,l1,h1,l2,h2,arr[50];
void main()
{
clrscr();
while(1)
{
scanf("%d",&choice);
switch(choice)
{
case 1:
Merge();
break;

case 2:
Quick();
break;

case 3:
Heap();
break;

case 4:
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;
}
}

{
struct node *tmp,*q;
int item;
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;
if(start==NULL)
start=tmp;
else
{
q=start;
}
}
printf("\n\n------------------------- ORIGINAL ARRAY ---------------------\n\n");
display1();
printf("\n\n---------------------------------- SORTED ARRAY --------------------\n\n");
display1();
}

void display1()
{
struct node *p=start;
printf("\n");
while( p !=NULL)
{
printf("%d\t ", p->info);
}

}

{
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] = p ;
}
printf("\n\nmindig=%d \t maxdig=%d",mindig,maxdig);
start=front[mindig];
for(i=mindig;i<maxdig;i++)
{
if(rear[i+1]!=NULL)
else
rear[i+1]=rear[i];
}
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;
}
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.