#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 int arr[500000];

double swp;
void selection_sort(int a[], int n)
{
    int i,j,min_index,temp;
    swp=0;
    for(i=0; i<n-1; i++)
    {
        min_index = i;
        for(j=i+1; j<n; j++)
        {
            if(a[j]<a[min_index])
            {
                min_index = j;
            }
        }
        if(min_index!=i)
        {
            temp = a[min_index];
            a[min_index]=a[i];
            a[i] = temp;
            swp++;
        }
    }
}
void insertion_sort(int a[],int n)
{
    int i,j,k,temp;
    swp=0;
    for(i=0; i<n; i++)
    {
        j=i;
        while(j>0&&a[j-1]>a[j])
        {
            temp=a[j];
            a[j]=a[j-1];
            a[j-1]=temp;
            j--;
            swp++;
        }
    }

}

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

int main()
{

    int maxx=100, i;
    clock_t start_time, end_time;
    double bubble_time;
    double selection_time;
    double insertion_time;

    //printf("Enter the Upper bound: ");
    //scanf("%d", &maxx);

    srand(time(0));
    for(i=0; i<1000; i++)
    {
        arr[i]=rand()%maxx+1;
    }

    start_time = clock();
    bubble_sort(arr,1000);
    end_time = clock();

    bubble_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for bubble sort 1000: %lf\n",bubble_time);

    start_time = clock();
    selection_sort(arr,1000);
    end_time = clock();

    selection_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for selection sort 1000: %lf\n",selection_time);

    start_time = clock();
    insertion_sort(arr,1000);
    end_time = clock();

    insertion_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for insertion sort 1000: %lf\n",insertion_time);


    /*for(i=0;i<1000;i++)
    {
        printf(" %d ",arr[i]);
    }

    printf("\n");
    */




    for(i=0; i<5000; i++)
    {
        arr[i]=rand()%maxx+1;
    }

    start_time = clock();
    bubble_sort(arr,5000);
    end_time = clock();

    bubble_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for bubble sort 5000: %lf\n",bubble_time);
    printf("swp = %lf\n",swp);
    start_time = clock();
    selection_sort(arr,5000);
    end_time = clock();


    printf("%d %d %d %d\n",arr[1],arr[2],arr[3],arr[4]);
    printf("%d\n",swp);

    selection_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for selection sort 5000: %lf\n",selection_time);
    printf("swp = %lf\n",swp);


    start_time = clock();
    insertion_sort(arr,5000);
    end_time = clock();

    insertion_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for insertion sort 5000: %lf\n",insertion_time);
    printf("swp = %lf\n",swp);

    for(i=0; i<10000; i++)
    {
        arr[i]=rand()%maxx+1;
    }

    start_time = clock();
    bubble_sort(arr,10000);
    end_time = clock();

    bubble_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for bubble sort 10000: %lf\n",bubble_time);
    printf("swp = %lf\n",swp);

    start_time = clock();
    selection_sort(arr,10000);
    end_time = clock();

    selection_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for selection sort 10000: %lf\n",selection_time);
    printf("swp = %lf\n",swp);

    start_time = clock();
    insertion_sort(arr,10000);
    end_time = clock();

    insertion_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for insertion sort 10000: %lf\n",insertion_time);
    printf("swp = %lf\n",swp);


    for(i=0; i<50000; i++)
    {
        arr[i]=rand()%maxx+1;
    }

    start_time = clock();
    bubble_sort(arr,50000);
    end_time = clock();

    bubble_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for bubble sort 50000: %lf\n",bubble_time);
    printf("swp = %lf\n",swp);
    start_time = clock();
    selection_sort(arr,50000);
    end_time = clock();

    selection_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for selection sort 50000: %lf\n",selection_time);
    printf("swp = %lf\n",swp);

    start_time = clock();
    insertion_sort(arr,50000);
    end_time = clock();

    insertion_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for insertion sort 50000: %lf\n",insertion_time);
    printf("swp = %lf\n",swp);

    for(i=0; i<100000; i++)
    {
        arr[i]=rand()%maxx+1;
    }

    start_time = clock();
    bubble_sort(arr,100000);
    end_time = clock();

    bubble_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for bubble sort 100000: %lf\n",bubble_time);
    printf("swp = %lf\n",swp);

    start_time = clock();
    selection_sort(arr,100000);
    end_time = clock();

    selection_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for selection sort 100000: %lf\n",selection_time);
    printf("swp = %lf\n",swp);

    start_time = clock();
    insertion_sort(arr,100000);
    end_time = clock();

    insertion_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for insertion sort 100000: %lf\n",insertion_time);
    printf("swp = %lf\n",swp);


    for(i=0; i<500000; i++)
    {
        arr[i]=rand()%maxx+1;
    }

    start_time = clock();
    bubble_sort(arr,500000);
    end_time = clock();

    bubble_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for bubble sort 500000: %lf\n",bubble_time);
    printf("swp = %lf\n",swp);
    start_time = clock();
    selection_sort(arr,500000);
    end_time = clock();

    selection_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("Time for selction sort 500000: %lf\n",selection_time);
    printf("swp = %lf\n",swp);

    start_time = clock();
    insertion_sort(arr,500000);
    end_time = clock();

    insertion_time = (double)(end_time-start_time)/CLOCKS_PER_SEC;
    printf("\nTime for insertion sort 500000: %lf\n",insertion_time);
    printf("swp = %lf\n",swp);



}