Sorting Method in C - program (bubble sort, insertion sort, linear sort, merge sort, quick sort, selection sort, redix sort, shell sort, heap sort)

Sorting Method in C - program
========================
(bubble sort, insertion sort, linear sort, merge sort, quick sort, selection sort, redix sort, shell sort, heap sort)


Bubble sort
===========

#include <stdio.h>
#include <conio.h>
void main ()
{
int a[20],n,i;
void bubble_sort(int [], int);
void display (int [], int);
clrscr ();
printf("Enter the number of elements you want to sort: ");
scanf("%d",&n);
printf("Enter the numbers\n");
for (i=0;i<n;i++)
scanf("%d",&a[i]);
bubble_sort (a,n);
display (a,n);
getch ();
}

void bubble_sort(int a[], int n)
{
int i,j,temp,exch,l;
l = n;
for (i = 0 ; i < n ; i++)
{
exch = 0;
for (j = 0 ;j < l - 1; j++)
{
if (a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
exch = exch + 1;
}
}
if (exch == 0)
return;
else
l = l-1;
}
}

void display (int a[], int n)
{
int i;
printf("The Output is:\n");
for (i = 0 ; i < n ; i++)
printf("%d ", a[i]);
}


Insertion sort
==============

#include <stdio.h>
#include <conio.h>
void main ()
{
int a[20],n,i;
void insertion_sort (int [], int);
void display (int [], int);
clrscr ();
printf("Enter the no. of elements you want to sort(less than 20): ");
scanf ("%d",&n);
printf("Enter %d elements:\n",n);
for (i = 0; i < n; i++)
scanf("%d",&a[i]);
insertion_sort(a,n);
display (a,n);
getch ();
}

void insertion_sort (int a[], int n)
{
int i, j, temp;
for (i = 1 ; i < n ; i++)
{
if (a[i] < a[i-1])
{
temp = a[i];
for (j = i-1 ; j >= 0 ; j--)
{
a[j+1] = a[j];
if(a[j-1] <= temp j == 0)
break;
}
a[j] = temp;
}
}
}

void display (int a[], int n)
{
int i;
printf("The Output is:\n");
for (i = 0 ; i < n ; i++)
printf("%d ",a[i]);
}


Linear Sort
===========

#include <stdio.h>
#include <conio.h>
void main ()
{
int a[20],n,i;
void linear_sort (int [], int);
void display (int [], int);
clrscr ();
printf("Enter the no. of elements you want to sort(less than 20): ");
scanf ("%d",&n);
printf("Enter %d elements:\n",n);
for (i = 0; i < n; i++)
scanf("%d",&a[i]);
linear_sort(a,n);
display (a,n);
getch ();
}

void linear_sort(int a[], int n)
{
int i, j, temp;
for (i=0; i<n; i++)
{
for (j=i+1; j<n; j++)
{
if(a[j] < a[i])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}

void display (int a[], int n)
{
int i;
printf("The Output is:\n");
for (i=0; i<n; i++)
printf("%d ",a[i]);
}



Merge Sort
===========

#include <stdio.h>
#include <conio.h>
void main ()
{
int n1,a1[20],n2,a2[20],a[40],result[40],i,j,k;

void merge_list(int[],int,int[],int,int[]);
int merge_sort (int[],int,int,int[]);
void display (int[],int);

clrscr ();

printf("\nEnter the number of elements you want to sort in the first list: ");
scanf("%d",&n1);

printf("\nEnter %d elements in the first list in sorted order\n",n1);
for (i=0;i<n1;i++)
scanf("%d",&a1[i]);

printf("\nEnter the number of elements you want to sort in the second list: ");
scanf("%d",&n2);

printf("\nEnter %d elements in the second list in sorted order\n",n2);
for (j=0;j<n2;j++)
scanf("%d",&a2[j]);

merge_list(a1,n1,a2,n2,a);
k = merge_sort(a,n1,n2,result);
display(result,k);

getch ();
}

void merge_list (int a1[],int n1,int a2[],int n2,int a[])
{
int i,j;
for (i=0;i<n1;i++)
a[i] = a1[i];
for (j=0;j<n2;j++)
a[n1+j] = a2[j];
}

int merge_sort (int a[],int n1,int n2,int result[])
{
int first,second,third,i,j,k=0;

first = 0;
second = n1;
third = n1+n2-1;
i = first;
j = second;

while (i<second && j<=third)
{
if (a[i] <= a[j])
{
result[k] = a[i];
i++;
}
else
{
result[k] = a[j];
j++;
}
k++;
}

if (i < second)
{
while (i < second)
{
result[k] = a[i];
i++;
k++;
}
}

if (j <= third)
{
while (j <= third)
{
result[k] = a[j];
j++;
k++;
}
}
return (k);
}

void display (int result[],int k)
{
int i;
printf("The sorted list is as follows:\n");
for (i=0;i<k;i++)
printf(" %d",result[i]);
}


Quick Sort
============

#include <stdio.h>
#include <conio.h>
void main ()
{
int a[20],n,lb,ub,i,j;
void quick_sort (int[],int,int);
void display (int[],int);
clrscr ();
printf("Enter no. of elements you want to sort: ");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
lb = 0;
ub = n-1;
quick_sort (a,lb,ub);
display (a,n);
getch ();
}

void quick_sort (int a[],int lb,int ub)
{
int i,j,key,flag=0,temp;
if (lb < ub)
{
i = lb;
j = ub+1;
key = a[i];
while (flag != 1)
{
i++;
while (a[i] < key)
i++;
j--;
while (a[j] > key)
j--;
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
else
{
flag = 1;
temp = a[lb];
a[lb] = a[j];
a[j] = temp;
}
}
quick_sort (a,lb,j-1);
quick_sort (a,j+1,ub);
}
}

void display (int a[],int n)
{
int i;
printf("The Output is:\n");
for (i=0;i<n;i++)
printf("%d ",a[i]);
}


Selection Sort
==============


#include <stdio.h>
#include <conio.h>
void main ()
{
int a[20],n,i;
void selection_sort (int [],int);
void display (int [],int);
clrscr ();
printf("Enter the no. of elements you want to sort: ");
scanf("%d",&n);
printf("Enter %d elements:\n",n);
for (i = 0 ; i < n ; i++)
scanf("%d",&a[i]);
selection_sort (a,n);
display (a,n);
getch ();
}

void selection_sort (int a[], int n)
{
int i,j,min,temp;
for (i = 0 ; i < n ; i++)
{
min = i;
for (j = i+1 ; j < n ; j++)
{
if (a[min] > a[j])
min = j;
}
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}

void display (int a[], int n)
{
int i;
printf("The Output is:\n");
for (i = 0 ; i < n ; i++)
printf("%d ",a[i]);
}


Redix sort
============

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

void main()
{

int arr[50],temparr[10][20],index[10];
int n,i,j,p,q,temp,m;
clrscr();
printf("Enter how many elements do you want to sort ? :");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element no %d ( don't enter -999 ): ",i+1);
scanf("%d",&arr[i]);
}

printf("The Sorted Elements BY REDIX SORT Are ");
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
temparr[i][j]=-999;
}
}


for( m=1 ; m<=5 ; m++ )
{
for(i=0;i<10;i++)
index[i]=0;
p=0;
for(j=0;j<n;j++)
{
temp = (double) pow( (double)10 , (double)m-1 );
p = (int)( arr[j] / temp ) % 10;
temparr[p][index[p]] = arr[j];
index[p] = index[p] + 1;
}
p=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if( temparr[i][j] != -999 )
{
arr[p] = temparr[i][j];
p++;
}
temparr[i][j] = -999;
}
}
}
for(i=0;i<n;i++)
printf("\n%d",arr[i]);
getch();
}


Shell Sort
==========

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

void shellsort(int arr[50],int n);
void main()
{

int arr[50];
int n,i,j,p,q,temp,m;
clrscr();
printf("Enter how many elements do you want to sort ? :");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element no %d : ",i+1);
scanf("%d",&arr[i]);
}

printf("The Sorted Elements BY SHELL SORT Are ");
shellsort(arr,n);
for(i=0;i<n;i++)
printf("\n%d",arr[i]);
getch();
}
void shellsort(int arr[50],int n)
{
int k,j,current,sorted,span,temp;
for( span = n/2 ; span>0 ; span = span/2 )
{
for(k=span;k<=n;k++)
{
current = arr[k];
j = k - span;
sorted = 0;
while((j >= 1) && (sorted == 0))
{
if(current < arr[j])
{
temp = arr[j+span];
arr[j+span] = arr[j];
arr[j] = temp;
j = j - span;
}
else
{
sorted = 1;
temp = arr[j+span];
arr[j+span] = current;
current = temp;
}
}
}
}
return;
}



Heap Sort
==========


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

void create_heap(int k[],int n)
{
int q,i,key,j,temp,g;

for (q=2;q<n;q++)
{
i=q;
key=k[q];
j=(int) i/2;
while(i>1 && key>k[j])
{
temp=k[i];
k[i]=k[j];
k[j]=temp;
i=j;
j=(int)i/2;
if(j<1)
j=1;
}
k[i]=key;

}
return;
}

void heap_sort(int k[],int n)
{
int q,temp,i,key,j,g;

create_heap(k,n);
printf("\n HEAP CREATED :- ");
for(i=1;i<n;i++)
printf(" %d ",k[i]);
printf("\n");
printf("\n Elements from heap :- ");
for(q=n;q>=2;q--)
{

temp=k[1];
k[1]=k[q];
k[q]=temp;
i=1;
key=k[1];
j=2;

if((j+1)<q)
{
if(k[j+1]>k[j])
j++;
}

while(j<=(q-1) && k[j]>key)
{
k[i]=k[j];
i=j;
j=2*i;
if((j+1)<q)
{
if (k[j+1]>k[j])
j++;
else
if (j>n)
j=n;
}
k[i]=key;
}
printf("\n AT q = %d ELEMENT FROM HEAP IS ==> %d",q,k[q]);
}
return;
}

void main()
{
int k[11]={0,42,23,124,11,5,58,94,1236,99,87},i;

clrscr();
printf("\n BEFORE HEAP SORT :- ");
for(i=1;i<11;i++)
printf(" %d ",k[i]);
heap_sort(k,11);

printf("\n AFTER HEAP SORT :- ");
for(i=2;i<=11;i++)
printf(" %d ",k[i]);
getch();
}