#include <stdlib.h>
#include <stdio.h>
//here is implementation of 6 main sorting algorithm ; data part is integer which is easily 
//extendable
//source code is free and is avaiable via public domain under GPL license
//all codes tested by gcc 3.32 from gnu and i used dev-c++  4.9.7.0 for developing
//by masoud kalali  21-22 jan 2003

//sorting algorithms implementation

void BubbleSort(int a[],int size){
    int switched = 1;
int hold;
    for(int i=0;i<size && switched;i++){
        switched = 0;
            for(int j=0;j<size-i;j++)
        if( a[j]>a[j+1] ){
            switched = 1;
            hold = a[j];
            a[j] = a[j+1];
            a[j+1] = hold;
        }
    }

    }
void SelectionSort(int a[],int size){
    for(int i = size;i>0;i--){
    int large = a[0];
        int indx = 0;
        for(int j = 1;j <= i;j++)
        if(a[j]>large ){
            large = a[j];
            indx = j;
        }
        a[indx] = a[i];
        a[i] = large;
    }
    }

  void InsertionSort(int a[],int size){
    int i,j;
    int e;
    for(i=1;i<size;i++){
        e = a[i];
        for(j=i-1;j>=0 && a[j]>(e);j--)
        a[j+1] = a[j];
        a[j+1] = e;
    }
    }

//an aray implementation of heapsort
 void HeapSort(int a[],int size){
    int i,f,s;
    for(i=1;i<size;i++){
        int e = a[i];
        s = i;
        f = (s-1)/2;
        while(s > 0 && a[f]>(e) ){
        a[s] = a[f];
        s = f;
        f = (s-1)/2;
        }
        a[s] = e;
    }
    for(i=size;i>0;i--){
        int value = a[i];
        a[i] = a[0];
        f = 0;
        if(i == 1)
        s = -1;
        else
        s = 1;
        if(i > 2 && a[2]>(a[1]))
        s = 2;
        while(s >= 0 && value<(a[s])){
        a[f] = a[s];
        f = s;
        s = 2*f+1;
        if(s+1 <= i-1 && a[s]<(a[s+1]) )
            s = s+1;
        if(s > i-1)
            s = -1;
        }
        a[f] = value;
    }
    }


//array implementation of merge sort
   void MergeSort(int x[], int n)
{
	long aux[8],i,j,k,L1,L2,size,U1,U2;
	size = 1; 
	while (size <n){
	  L1 = 0;
	  k = 0;
	  while (L1+size < n){ 
  	     L2 = L1 + size;
	     U1 = L2 - 1;
	     U2 = (L2+size-1 < n) ? L2+size-1 : n-1;
 	     for (i=L1, j=L2; i<=U1 && j<=U2; k++)
			if (x[i] <= x[j])
				aux[k] = x[i++];
			else
				aux[k] = x[j++];
		for (; i<=U1;k++)
			aux[k] = x[i++];
		for (; j <=U2;k++)
			aux[k] = x[j++];
		L1 = U2 + 1;
	   } 
	   for (i = L1; k<n; i++)
		aux[k++] = x[i];
	   for (i=0; i<n;i++)
		x[i] = aux[i];
	   size *=2;
	}
}


void quick(int a[],int left,int right)
{
int i,j;
int x,temp;
i=left;
j=right;
x=a[(left+right)/2];
do{
  while(a[i]<x&& i<right) ++i;
  while(a[j]>x && j>left)  --j;
  if (i<=j)
  {
temp=a[i];
a[i]=a[j];
a[j]=temp;
     ++i;
     --j;
  }
  } while(i<=j);
  if (left<j)quick(a,left,j);
  if (i<right)quick(a,i,right);
}
//end of algorithms implementation



int main(void)
{
int i;
int a[100];
//checking buble sort
for(int i=0 ;i<=9;i++) a[i]=random();
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
BubbleSort(a,10);
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
//checking selection sort
printf("selection sort\n");
for(int i=0 ;i<=9;i++) a[i]=random();
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
SelectionSort(a,10);
printf("\n");printf("\n");
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
//checking insertion sort
printf("insertion sort sort\n");
for(int i=0 ;i<=9;i++) a[i]=random();
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
InsertionSort(a,10);
printf("\n");
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
//checking heap sort
printf("heap sort test\n");
for(int i=0 ;i<=9;i++) a[i]=random();
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
HeapSort(a,10);
printf("\n");
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
//checking merg sort
printf("merg sort test\n");
for(int i=0 ;i<=9;i++) a[i]=random();
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
MergeSort(a,10);
printf("\n");
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
//checking quicksort sort
printf("quick sort sort test\n");
for(int i=0 ;i<=9;i++) a[i]=random();
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\n");
quick(a,0,9);
printf("\n");
for(int i=0 ;i<=9;i++) printf("%D\n",a[i],' ',' ',' ');
printf("\nc");
}