Code:
/*Program of sorting using quick sort through recursion*/
#include<stdio.h>
#include<conio.h>
#define MAX 30
enum bool { FALSE,TRUE };
void main()
{
int a[MAX],n,i;
clrscr();
printf("Enter the number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted list is :\n");
display(a,0,n-1);
printf("\n");
quick(a,0,n-1);
printf("Sorted list is :\n");
display(a,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--;
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++;
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]);
getch();
}
Code:
/*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()*/
Code:
/*Program of sorting using selection sort*/
#include<stdio.h>
#include<conio.h>
#define MAX 20
void main()
{
int arr[MAX],i,j,k,n,temp,smallest;
clrscr();
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");
getch();
}/*End of main()*/
Code:
/* Program of sorting using shell sort */
#include <stdio.h>
#define MAX 20
main()
{
int arr[MAX], i,j,k,n,incr;
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("\nEnter maximum increment (odd value) : ");
scanf("%d",&incr);
/*Shell sort*/
while(incr>=1)
{
for(j=incr;j<n;j++)
{
k=arr[j];
for(i = j-incr; i >= 0 && k < arr[i]; i = i-incr)
arr[i+incr]=arr[i];
arr[i+incr]=k;
}
printf("Increment=%d \n",incr);
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
incr=incr-2; /*Decrease the increment*/
}/*End of while*/
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/
Code:
/* HEAP SORT */
/* HEAP.C */
# include<stdio.h>
void heap_sort(int *, int );
void create_heap(int *, int);
void display(int *, int);
/* Definition of the function */
void create_heap(int list[], int n )
{
int k, j, i, temp;
for(k = 2 ; k <= n; ++k)
{
i = k ;
temp = list[k];
j = i / 2 ;
while((i > 1) && (temp > list[j]))
{
list[i] = list[j];
i = j ;
j = i / 2 ;
if ( j < 1 )
j = 1 ;
}
list[i] = temp ;
}
}
/* End of heap creation function */
/* Definition of the function */
void heap_sort(int list[], int n)
{
int k, temp, value, j, i, p;
int step = 1;
for(k = n ; k >= 2; --k)
{
temp = list[1] ;
list[1] = list[k];
list[k] = temp ;
i = 1 ;
value = list[1];
j = 2 ;
if((j+1) < k)
if(list[j+1] > list[j])
j ++;
while((j <= ( k-1)) && (list[j] > value))
{
list[i] = list[j];
i = j ;
j = 2*i ;
if((j+1) < k)
if(list[j+1] > list[j])
j++;
else
if( j > n)
j = n ;
list[i] = value;
} /* end of while statement */
printf("\n Step = %d ", step);
step++;
for(p = 1; p <= n; p++)
printf(" %d", list[p]);
} /* end for loop */
}
/* Display function */
void display(int list[], int n)
{
int i;
for(i = 1 ; i <= n; ++ i)
{
printf(" %d", list[i]);
}
}
/* Function main */
void main()
{
int list[100];
int i, size = 13 ;
printf("\n Size of the list: %d", size);
for(i = 1 ; i <= size ; ++i)
{
list[i] = rand() % 100;
}
printf("\n Entered list is as follows:\n");
display(list, size);
create_heap(list, size);
printf("\n Heap\n");
display(list, size);
printf("\n\n");
heap_sort(list,size);
printf("\n\n Sorted list is as follows :\n\n");
display(list,size);
}
OUTPUT:
Size of the list: 13
Entered list is as follows:
41 67 34 0 69 24 78 58 62 64 5 45 81
Heap
81 67 78 62 64 69 34 0 58 41 5 24 45
Step = 1 78 67 69 62 64 45 34 0 58 41 5 24 81
Step = 2 69 67 45 62 64 24 34 0 58 41 5 78 81
Step = 3 67 64 45 62 41 24 34 0 58 5 69 78 81
Step = 4 64 62 45 58 41 24 34 0 5 67 69 78 81
Step = 5 62 58 45 5 41 24 34 0 64 67 69 78 81
Step = 6 58 41 45 5 0 24 34 62 64 67 69 78 81
Step = 7 45 41 34 5 0 24 58 62 64 67 69 78 81
Step = 8 41 24 34 5 0 45 58 62 64 67 69 78 81
Step = 9 34 24 0 5 41 45 58 62 64 67 69 78 81
Step = 10 24 5 0 34 41 45 58 62 64 67 69 78 81
Step = 11 5 0 24 34 41 45 58 62 64 67 69 78 81
Step = 12 0 5 24 34 41 45 58 62 64 67 69 78 81
Sorted list is as follows :
0 5 24 34 41 45 58 62 64 67 69 78 81
Press any key to continue
Bubble Sort
Code:
/* bubble.c */
#include <stdio.h>
#include <stdlib.h>
void bubble_sort(int array[], int size)
{
int temp, i, j;
for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (array[i] < array[j])
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
void main(void)
{
int values[30], i;
printf("\n Unsorted list is as follows\n");
for (i = 0; i < 10; i++)
{
values[i] = rand() % 100;
printf(" %d", rand()%100);
}
bubble_sort(values, 10);
printf("\n Sorted list is as follows\n");
for (i = 0; i < 10; i++)
printf("%d ", values[i]);
}
OUTPUT:
Unsorted list is as follows
67 0 24 58 64 45 27 91 42 36
Sorted list is as follows
27 34 41 61 62 69 78 81 95
Press any key to continue
Code:
/* Insertion sort */
/* INSERT.C */
# include<stdio.h>
# include<stdlib.h>
void insertion_sort(int *, int);
void display(int*, int);
void insertion_sort(int l[], int n)
{
int pointer, temp;
int i, k;
l[0] = -0;
for(i = 1 ; i <= n; i++)
{
pointer = i -1;
temp = l[i];
while(temp < l[pointer])
{
l[pointer+1] = l[pointer];
pointer --;
}
l[pointer+1] = temp;
printf("Step = %d", i);
for(k = 0; k <= n; k++)
printf(" %d", l[k]);
printf("\n");
}
}
void display(int l[], int n)
{
int i;
printf("\n Sorted list is as follows\n");
for(i = 1; i <= n; i++)
printf(" %d", l[i]);
}
void main()
{
int number = 10;
int list[100];
int i;
printf("\n Number of elements in the list: %i", number);
printf("\n Unsorted list is as follows \n");
for(i = 1; i <= number; i++)
{
list[i] = rand() %100;
printf(" %d", rand() %100);
}
printf("\n");
printf("\n Step wise result is as follows \n\n");
insertion_sort(list,number);
display(list, number);
}
OUTPUT:
Number of elements in the list: 10
Unsorted list is as follows
67 0 24 58 64 45 27 91 42 36
Step wise result is as follows
Step = 1 0 41 34 69 78 62 5 81 61 95 27
Step = 2 0 34 41 69 78 62 5 81 61 95 27
Step = 3 0 34 41 69 78 62 5 81 61 95 27
Step = 4 0 34 41 69 78 62 5 81 61 95 27
Step = 5 0 34 41 62 69 78 5 81 61 95 27
Step = 6 0 5 34 41 62 69 78 81 61 95 27
Step = 7 0 5 34 41 62 69 78 81 61 95 27
Step = 8 0 5 34 41 61 62 69 78 81 95 27
Step = 9 0 5 34 41 61 62 69 78 81 95 27
Step = 10 0 5 27 34 41 61 62 69 78 81 95
Sorted list is as follows
5 27 34 41 61 62 69 78 81 95Press any key to continue
Code:
/* MERGE SORT */
/* merge.c */
# include<stdio.h>
# include<stdlib.h>
void merge_sort(float *, int , int , int );
void merge_pass(float *, int , int );
/* Definition of the function */
void merge_sort(float l[], int top, int size, int bottom)
{
float temp[1000];
int f = top;
int s = size +1 ;
int t = top ;
int upper;
while(( f <= size)&&(s <=bottom))
{
if(l[f] <= l[s])
{
temp[t] = l[f] ;
f ++;
}
else
{
temp[t] = l[s] ;
s ++;
}
t ++;
}
if(f <=size)
{
for(f = f ; f<=size; f++)
{
temp[t] = l[f];
t++;
}
}
else
{
for(s = s ; s<= bottom ; s++)
{
temp[t]=l[s];
t++;
}
}
for(upper = top; upper <= bottom ; upper++)
{
l[upper]=temp[upper];
}
}
/* Definition of the function */
void merge_pass( float append[], int m, int n )
{
if( m!= n)
{
int mid = (m+n)/2;
merge_pass( append, m, mid );
merge_pass( append, mid+1, n );
merge_sort( append, m, mid, n );
}
}
/* main function */
void main()
{
float list[1000];
int i, n = 30;
printf("\n Size of the list: %d", n);
for(i = 0 ; i < n ; i++)
{
list[i] = (float) (rand() %100);
}
printf("\n Entered list as follows:\n");
for( i = 0 ; i<n ; i++)
printf(" %d ", (int) list[i]);
i = 0 ;
merge_pass(list, i, n-1);
printf("\n Merge sorted list is as follows:\n");
for( i = 0 ; i<n ; i++)
printf(" %d", (int) list[i]);
}
OUTPUT:
Size of the list: 30
Entered list as follows:
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 9
1 4 2 53 92 82 21 16 18 95
Merge sorted list is as follows:
0 2 4 5 16 18 21 24 27 27 34 36 41 42 45 53 58 61 62 64 67 69 78 81 82 91 91 92
95 95
Press any key to continue
Currently Active Users
Categories
Latest Blog Entries
Rate this article