Bubble sort:
#include<stdio.h>
// compare adjacent elements and swap if needed until whole is not sorted
int arr[]={3,8,6,1,9,6,3,1,10,7,8,5,16};
int size;
void main()
{
size=sizeof(arr)/sizeof(int);
int out[size];
int i,j;
for(i=size-1;i>=0;i--)
{
for(j=0;j<i-1;j++)
{
if(arr[j]>arr[j+1])
{
int tmp;
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
printf("size= %d\n",size);
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
Selection sort:
#include<stdio.h>
// find minimum and bring it to top
int arr[]={3,8,6,1,9,6,3,1,10,7,8,5,16};
int size;
void main()
{
size=sizeof(arr)/sizeof(int);
int out[size];
int i,j;
for(i=0;i<size-1;i++)
{
for(j=i+1;j<size;j++)
{
if(arr[i]>arr[j])
{
int tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
}
printf("size= %d\n",size);
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
Insertion sort:
#include<stdio.h>
// insert element at right place in list
int arr[]={8,3,6,1,9,6,3,1,10,7,8,5,16};
int size;
void main()
{
size=sizeof(arr)/sizeof(int);
int out[size];
int i,j,v;
for(i=1;i<size;i++)
{
v=arr[i];
j=i;
while(arr[j-1]>v&&j>=1)
{
arr[j]=arr[j-1];
j--;
}
arr[j]=v;
}
printf("size= %d\n",size);
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
------------------------------------------------------------------
Quick sort:
-----------------------------------------------------------------
#include<stdio.h>
int a[]={4,2,7,8,5,1,0,6};
int size;
void print()
{
int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
}
void swap(int left,int right)
{
int tmp=a[left];
a[left]=a[right];
a[right]=tmp;
}
int partition(int l,int r)
{
int x=a[l];
int left=l;
int right=r;
while(left<right)
{
while(a[left]<=x)
left++;
while(a[right]>x)
right--;
if(left<right)
swap(left,right);
}
a[l]=a[right];
a[right]=x;
//printf("\nPivot= %d ",a[right]);
//print();
//printf("\n");
return right;
}
void quicksort(int l,int r)
{
//
printf("%d %d\n",l,r);
int i;
if(r>l)
{
int p=partition(l,r);
quicksort(l,p-1);
quicksort(p+1,r);
}
}
void main()
{
size=sizeof(a)/sizeof(a[0]);
//print();
int p=0;
int l=0,r=size;
quicksort(l,r);
print();
}
----------------------------------------------------------
Merge Sort:
----------------------------------------------------------
#include<stdio.h>
int a[]={3,3,6,1,9,6,3,1,10,7,8,5,16};
int size;
int tmp[13];
void merge(int l,int m,int r)
{
int tmp[r-l+1];
int p=0;
int i=0,j=0;
if(a[l]>a[r])
{
for(i=m;i<r+1;i++)
tmp[p++]=a[i];
for(i=l;i<m;i++)
tmp[p++]=a[i];
}
else if(a[m]>a[m-1])
{
for(i=l;i<m;i++)
tmp[p++]=a[i];
for(i=m;i<r+1;i++)
tmp[p++]=a[i];
}
else
{
i=l;
j=m;
while((i<m)&&(j<r+1))
{
{
tmp[p++]=a[i++];
}
else if(a[i]>a[j])
{
tmp[p++]=a[j++];
}
else
tmp[p++]=a[i++];
}
if(i<m)
{
//printf("\nIn case 1\n");
int q;
for(q=i;q<m;q++)
{
tmp[p++]=a[q];
}
}
else if(j<r+1)
{
// printf("\nIn case 2p=%d\n",p);
int q;
for(q=j;q<r+1;q++)
{
tmp[p++]=a[q];
}
}
}
for(i=l;i<r+1;i++)
{
a[i]=tmp[i-l];
}
}
void mergesort(int l,int r)
{
int m;
if(r>l)
{
m=(l+r)/2;
mergesort(l,m);
mergesort(m+1,r);
merge(l,m+1,r);
}
}
void main()
{
size=sizeof(a)/sizeof(a[0]);
int l=0,r=size-1;
mergesort(l,r);
int i;
for(i=0;i<size;i++)
printf("%d ",a[i]);
}
--------------------------------------------------
Counting sort:
-------------------------------------------------
#include<stdio.h>
int a[]={1,5,6,4,8,9,3,8,0,10,16,21,6};
int size,max;
void main()
{
size=sizeof(a)/sizeof(a[0]);
int i;
int out[size];
max=0;
for(i=0;i<size;i++)
{
if(a[i]>max)
max=a[i];
}
int c[max+1];
for(i=0;i<max+1;i++)
{
c[i]=0;
}
for(i=0;i<size;i++)
{
c[a[i]]=c[a[i]]+1;
}
for(i=1;i<max+1;i++)
{
c[i]=c[i]+c[i-1];
}
for(i=size;i>=0;i--)
{
out[c[a[i]]-1]=a[i];
c[a[i]]=c[a[i]]-1;
}
for(i=0;i<size;i++)
{
printf("%d ",out[i]);
}
}
