Bubble Sort

/**** C Program For Implementation Of Bubble Sort. Sorting names entered by the user *****/
#include< stdio.h>
#include< conio.h>
#define MAX 10

char name[MAX][15];
void sort(int n)
{
int pa,cp,i,j,k,kk=0;
char temp[15];
pa=n-1;
cp=n-1;
for(i=1;i< =pa;i++)
{
for(j=1;j< =cp;j++)
{
kk=kk+1;
if(strcmp(name[j],name[j+1])>0)
{
strcpy(temp,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],temp);
}
}
printf("\n List after %d pass is ",i);
for(k=1;k< =n;k++)
printf("\n\t\t %s",name[k]);
getch();
}
clrscr();
printf("\n\t\t Total Comparisions Done : %d",kk);
}

void main()
{
int n,i,j;
clrscr();
printf("Enter How Many Names : ");
scanf("%d",&n);
if(n>MAX)
printf("\n\t\tArray Size IS Only %d",MAX);
else
{
printf("\n\t\tEnter %d Names :\n",n);
for(i=1;i< =n;i++)
{
printf("\t\t");
scanf("%s",name[i]);
}
sort(n);
printf("\n\n\t\tSorted List ");
for(i=1;i< =n;i++)
printf("\n\t\t%s",name[i]);
}
getch();
}
/********************* OUTPUT *******************
Enter How Many Names : 4

Enter 4 Names :
Malcolm
Lionel
Mayank
Pinto

List after 1 pass is
Lionel
Malcolm
Mayank
Pinto
List after 2 pass is
Lionel
Malcolm
Mayank
Pinto
List after 3 pass is
Lionel
Malcolm
Mayank
Pinto

*/

Heap Sort

/************* C Program To Sort An Array Using Heap Sort *************/

#include < stdio.h>
#include < conio.h>

void swap(int *x,int *y)
{
int temp;
temp=*x;
*x = *y;
*y = temp;
}

void heapsort(int a[],int n)
{
int i,s,f;
for(i=1;i< n;++i)
{
s=i;
f=(s-1)/2;
while( a[f]< a[s])
{
swap(&a[f],&a[s]);
s=f;
if(s==0)
break;
f=(s-1)/2;
}
}
for(i=n-1;i>=1;--i)
{
swap(&a[0],&a[i]);
f=0;
s=1;
if(i==1)
break;
if(i>2)if(a[2]>a[1])s=2;
while( a[f]< a[s] )
{
swap(&a[f],&a[s]);
f=s;
s=2*f+1;
if(i>s+1 )if(a[s+1]>a[s])s=s+1;
if (s>=i)
break;
}
}
}


void main()
{
int a[100],n,i;
clrscr();
printf("\t\tHEAP SORT\n");
printf("\nEnter The Number Of Elements\t: ");
scanf("%d",&n);
printf("\nEnter Elements\n");
for(i=0;i< n;++i)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\n\t\t\tSorted List\n");
for(i=0;i< n;++i)
printf("\t%d",a[i]);
getche();
}
/***************** OUTPUT ******************
HEAP SORT

Enter The Number Of Elements : 6

Enter Elements
45
12
3
1
78
6

Sorted List
1 3 6 12 45 78
*/

Radix Sort Algorithm

/* C program to sort an array using radix sort LINKED LIST implementation*/

#include < stdio.h>
#include < conio.h>
#include < stdlib.h>

void radix(int a[],int n,int m)
{
typedef struct node
{
int data;
struct node * next;
}NODE;

NODE * ptr,*start,*prev;
NODE *front[10], *rear[10];
int k=1,i,j,y,p;;
/*creating initial linked list*/
start=NULL;
for(i=0;i< n;++i)
{
ptr=(NODE *)malloc(sizeof(NODE));
ptr->data=a[i];
ptr->next=NULL;
if(start==NULL)
start=ptr;
else
prev->next=ptr;
prev=ptr;
}

/*radix sort*/

for(i=1;i< =m;++i)
{
for(j=0;j< 10;++j)
front[j]=NULL;
/*placing elements into queues*/
ptr=start;
while(ptr!=NULL)
{y=ptr->data/k %10;/*y is the digit*/
if(front[y]==NULL)
{
front[y]=ptr;
rear[y]=ptr;
}
else
{
rear[y]->next=ptr;
rear[y]=ptr;
}

ptr=ptr->next;
}

start=NULL;
for(j=0;j< 10;++j)
if(front[j]!=NULL)
{
if(start==NULL)
start=front[j];
else rear[p]->next=front[j];
p=j;
}
rear[p]->next=NULL;
k=k*10;
}
/*copying back to array*/
ptr=start;
for(i=0;i< n;++i,ptr=ptr->next)
a[i]=ptr->data;

}

void main()
{
int a[100],n,i,m;
char temp;
do
{
clrscr();
printf("===========================RADIX SORT===========================================\n");
printf("ENTER NUMBER OF NUMBERS AND NUMBER OF DIGITS\n");
scanf("%d%d",&n,&m);
printf("ENTER ELEMENTS\n");
for(i=0;i< n;++i)
scanf("%d",&a[i]);
radix(a,n,m);
printf("SORTED LIST\n");
for(i=0;i< n;++i)
printf("%d ",a[i]);
printf("\nDO YOU wish to continue?[y/n]\n");
scanf("%c",&temp);


}while(temp=='y'|| temp=='Y');
printf("\n---------------------------------------------------------------------------------\n");
getch();
}
/*OUTPUT:
===========================RADIX SORT===========================================

Enter number of numbers and number of digits
4
2
enter elements
25
65
35
45
sorted list
25 35 45 65
Do you wish to continue?[y/n]
n
--------------------------------------------------------------------------------*/

Shuttle Sort - Simple Insertion Sort

#include< stdio.h>
#include< conio.h>

void shutsort(int a[],int n)
{
int j,i=1,mid;

while(i< n)
{
j=i-1;
while(j>=0)
{
if(a[j]>a[j+1])
{
mid = a[j];
a[j] = a[j+1];
a[j+1]=mid;
j--;
}
else
break;
}
i++;
}
}

main()
{
int a[10],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
shutsort(a,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT
Enter The number Of Elements : 5

Element 1 : 21

Element 2 : 36

Element 3 : 54

Element 4 : 98

Element 5 : 1

Array Befor Sorting : 21 36 54 98 1
Array After Sorting : 1 21 36 54 98
*/

Shell Sort

#include< stdio.h>
#include< conio.h>

void shellsort(int a[],int n)
{
int j,i,k,m,mid;
for(m = n/2;m>0;m/=2)
{
for(j = m;j< n;j++)
{
for(i=j-m;i>=0;i-=m)
{
if(a[i+m]>=a[i])
break;
else
{
mid = a[i];
a[i] = a[i+m];
a[i+m] = mid;
}
}
}
}
}

main()
{
int a[10],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
shellsort(a,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT

Enter The number Of Elements : 5

Element 1 : 21

Element 2 : 36

Element 3 : 54

Element 4 : 2

Element 5 : 0

Array Befor Sorting : 21 36 54 2 0
Array After Sorting : 0 2 21 36 54
*/

Merge Sort

#include< stdio.h>
#include< conio.h>

void mergesort(int a[],int n)
{
int b[50],c,low1,high1,high2,low2;
int i,k,j;
c=1;
while(c< n)
{
low1=0;
k=0;
while(low1+c< n)
{
low2=low1+c ;
high1=low2-1;
if(low2+c-1< n)
high2=low2+c-1;
else
high2=n-1;
i=low1;
j=low2;
while(i< =high1 && j< =high2)
{
if(a[i]< =a[j])
b[k++] =a[i++];
else
b[k++] = a[j++];

}
while(i< =high1)
b[k++]=a[i++];
while(j< =high2)
b[k++] =a[j++];
low1=high2+1;
}
i=low1;
while(k< n)
b[k++] =a[i++];
for(i=0;i< n;i++)
a[i]=b[i];
c=c*2;
}
}

main()
{
int a[20],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
mergesort(a,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}

/* OUTPUT

Enter The number Of Elements : 10

Element 1 : 12

Element 2 : 54

Element 3 : 98

Element 4 : 6566

Element 5 : 45

Element 6 : 12

Element 7 : 5

Element 8 : 1

Element 9 : 156

Element 10 : 21

Array Befor Sorting : 12 54 98 6566 45 12 5 1 156 21
Array After Sorting : 1 5 12 12 21 45 54 98 156 6566


*/

Quicksort

#include< stdio.h>
#include< conio.h>

void quicksort(int [],int,int);
int partition(int [],int,int);


main()
{
int a[20],p,q,i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

p=0;
q=n-1;
printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
quicksort(a,p,q);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
getch();
return 0;
}


void quicksort(int a[],int p,int q)
{
int j;
if(p< q)
{
j=partition(a,p,q+1);
quicksort(a,p,j-1);
quicksort(a,j+1,q);
}
}

int partition(int a[],int m,int p)
{
int v,i,j;
int temp;
v=a[m];
i=m;j=p;
do
{
do
{
i += 1;
}
while(a[i]< v);
do
{
j -= 1;
}
while(a[j]>v);

if(i< j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
while(i< j);
a[m] =a[j];
a[j] = v;
return j;
}

/* OUTPUT

Enter The number Of Elements : 10

Element 1 : 12

Element 2 : 54

Element 3 : 98

Element 4 : 6566

Element 5 : 45

Element 6 : 12

Element 7 : 5

Element 8 : 1

Element 9 : 156

Element 10 : 21

Array Befor Sorting : 12 54 98 6566 45 12 5 1 156 21
Array After Sorting : 1 5 12 12 21 45 54 98 156 6566


*/

Simple Selection Sort

#include< stdio.h>
#include< conio.h>

void simplesel(int a[],int b[],int n)
{
int j,i=0,k,H;
int L=32760;
k=0;
L=H;
while(i< n)
{
for(j=0;j< n;j++)
{
if(a[j]< L)
{
L = a[j];
k = j;
}
}
a[k] = H;
b[i] = L;
L = H;
i++;
}
}

main()
{
int a[10],b[10],i,n;
clrscr();

printf("Enter The number Of Elements\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("\nElement %d\t: ",i+1);
scanf("%d",&a[i]);
}

printf("\nArray Befor Sorting : ");
for(i=0;i< n;i++)
printf("%5d",a[i]);
simplesel(a,b,n);

printf("\nArray After Sorting : ");
for(i=0;i< n;i++)
printf("%5d",b[i]);
getch();
return 0;
}
/* OUTPUT
Enter The number Of Elements : 10

Element 1 : 21

Element 2 : 25

Element 3 : 63

Element 4 : 45

Element 5 : 1

Element 6 : 147

Element 7 : 10

Element 8 : 78

Element 9 : 96

Element 10 : 5
Array Befor Sorting : 21 25 63 45 1 147 10 78 96 5
Array After Sorting : 1 5 10 21 25 45 63 78 96 147
*/

Binary Tree Sort

This has two phases. First phase is creating a binary search tree using the given array elements. Second phase is traverse the given binary search tree in inorder, thus resulting in a sorted array.

Performance
The average number of comparisons for this method is O(nlog₂n)
But in the worst case, the number of comparisons are reduced by O(n²), a case which arises when the sort tree is severely unbalanced .


/****** C Program For Implementation Of Binary Sort ***/

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *rightchild;
int data;
struct btreenode *leftchild;
};

insert(struct btreenode **sr,int num)
{
if(*sr==NULL)
{
*sr=malloc(sizeof(struct btreenode));

(*sr)- >leftchild=NULL;
(*sr)- >data=num;
(*sr)- >rightchild=NULL;
return;
}
else
{
if(num< (*sr)- >data)
insert(&((*sr)- >leftchild),num);
else
insert(&((*sr)- >rightchild),num);
}
return;
}

inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr- >leftchild);
printf("%d ",sr- >data);
inorder(sr- >rightchild);
}
else
return;
}

postorder(struct btreenode *sr)
{
if(sr!=NULL)
{
postorder(sr- >rightchild);
printf("%d ",sr- >data);
postorder(sr- >leftchild);
}
else
return;
}

void main()
{
struct btreenode *bt;
int req,i=0,num,a[10],no;

bt=NULL;
clrscr();

while(i < 5)
{
printf("\nEnter value to be inserted: ");
scanf("%d",&a[i]);
insert(&bt,a[i]);
i++;
}
clrscr();
printf("\n\nSorted Binary tree in ascending order== > \n\n");
inorder(bt);
printf("\n\nSortred binary tree in descending order== >\n\n");
postorder(bt);
getch();
}


/************************** OUTPUT ***********************

Enter value to be inserted: 9

Enter value to be inserted: 8

Enter value to be inserted: 4

Enter value to be inserted: 5

Enter value to be inserted: 7


Sorted Binary tree in ascending order== >

4 5 7 8 9

Sortred binary tree in descending order== >

9 8 7 5 4 */

Straight Selection Sort

One of the easiest sorting methods is selection sort. Beginning with the first element of the given array, a search is made to find the largest element in the array. When the element is found this element is interchanged with the last element of the array. Now the size of the unsorted array will be reduced but one. A search for the largest element of the unsorted array is carried out. When this element is found it will be interchanged with the last element of the unsorted array. Once again the unsorted array will be reduced by 1 and the above process will be repeated till the entire array is sorted in ascending order.

ALGORITHM
1. Establish an array ‘a’ with ‘n’ elements
2. Repeat through step 6 for ‘n-1’ times
3. Repeat the position of the array already sorted
4. Repeat step 5 for the elements in unsorted position of the array
5. Record location of the largest element in the unsorted array
6. Exchange last element in the unsorted array with the largest element

PERFORMANCE OF THE ALGORITHM
During the first pass, in which the largest element is found, n-1 elements are compared. In general, for ith pass of the sort, n-I comparisons are required

So total number of comparisons
n-1 + n-2 + ……… + 1

Time Complexity = O(n²)

/**** C Program For Implementation Of Selection Sort ****/

#define MAX 10
char name[MAX][15];
void sort(int n)
{
int i,j,index;
char temp[15];
for(i=n;i >0;i--)
{
strcpy(temp,name[1]);
index=1;
for(j=1;j< =i;j++) { if(strcmp(name[j],temp) >0)
{
strcpy(temp,name[j]);
index=j;
}
}
strcpy(name[index],name[i]);
strcpy(name[i],temp);
}
}
void main()
{
int i,j,n;
clrscr();
A: printf("\n\nENTER HOW MANY NAMES: ");
scanf("%d",&n);
if(n >MAX)
{
printf("\n\t\tARRAY SIZE IS ONLY %d",MAX);
goto A;
}
else
{
printf("\n\t ENTER %d Names : \n",n);
for(i=1;i< =n;i++) { printf("\t\t"); scanf("%s",name[i]); } sort(n); printf("\n\n\t\t*********** SORTED LIST ************"); for(i=1;i< =n;i++) printf("\n \t\t\t\t%s",name[i]); } getch(); } /********** OUTPUT ************** ENTER HOW MANY NAMES: 12 ARRAY SIZE IS ONLY 10 ENTER HOW MANY NAMES: 4 ENTER 4 Names : Lionel Cyril Valerian Noronha *********** SORTED LIST ************ Cyril Lionel Noronha Valerian **************************************/

Merge Sort

Merging is the process of combining two or more sorted arrays into a third sorted array. We can use this technique to sort an array of n elements as follows.
Divide the array into ‘n’ sub arrays of size 1 and merge adjacent pairs of sub arrays. Then we can have approximately n/2 sorted sub arrays of size 2. Repeat this process until there is 1 array containing n elements.
Algorithm
1. Establish a sub array ‘a’ with n elements
2. Let size < - 1 3. Repeat steps 4 through 6 until size >= n
4. Subdivide the sub array into sub arrays of size ‘size’
5. Merge adjacent pairs of sub arrays
6. Double the size

/*** C Program For Implementation Of Merge Sort ***/

#define MAX 20

void mergesort(int *,int);
void main()
{
int x[MAX],n,j,i;
char ans;
clrscr();
{
printf("\nEnter The Length Of The Array\t: ");
scanf("%d",&n);
for(i=0;i< n;i++)
{
printf("Enter Element %d\t: ",i+1);
scanf("%d",&x[i]);
}
mergesort(x,n);
printf("\n\t│ Sorted Array :\t\t\t│\n\t│");
for(i=0;i< n;i++)
printf("%d\t",x[i]);
}
printf("│");
getch();
}

void mergesort(int x[],int n)
{
int sub[MAX];
int i,j,k,list1,list2,u1,u2,size=1;
while(size< n)
{
list1=0;
k=0;

while((list1+size)< n)
{
list2=list1+size;
u1=list2-1;
u2=((list2+size-1)< n)?(list2+size-1):(n-1);

for(i=list1,j=list2;i< =u1 &&amp;amp;amp; j< =u2;k++)
if(x[i]< =x[j])
sub[k]=x[i++];
else
sub[k]=x[j++];

for(;i< =u1;k++)
sub[k]=x[i++];

for(;j< =u2;k++)
sub[k]=x[j++];

list1=u2+1;
}
for(i=list1;k< n;i++)
sub[k++] = x[i];
for(i=0;i< n;i++)
x[i] =sub[i];
size *= 2;
}
}
/********* OUTPUT **********

Enter The Length Of The Array : 5
Enter Element 1 : 12
Enter Element 2 : 69
Enter Element 3 : 78
Enter Element 4 : 2
Enter Element 5 : 5

│ Sorted Array : │
│2 5 12 69 78 │
*/