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 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.

1 comment: