#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int array[500009];
long swap_count = 0;

void bubble_sort(int a[], int n)
{
    int i,j,temp;
    long comp_count = 0;
    clock_t start_time, end_time;
    double time_passed;

    start_time = clock();
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            comp_count++;
            if(a[j]>a[j+1])
            {
                swap_count++;
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
    end_time = clock();
    time_passed = (double)(end_time - start_time)/CLOCKS_PER_SEC;

    printf("\nTime: %lf",time_passed);
    printf("\nSwap count: %ld",swap_count);
    printf("\nComp count: %ld\n",comp_count);
}

void selection_sort(int a[], int n)
{

    int i,j,index_min,temp;
    long comp_count = 0;
    clock_t start_time, end_time;
    double time_passed;

    start_time = clock();
    for(i=0; i<n-1; i++)
    {
        index_min = i;
        for(j=i+1; j<n; j++)
        {
            comp_count++;
            if(a[j] < a[index_min])
            {
                index_min = j;
            }
        }
        if(index_min != i)
        {
            swap_count++;
            temp = a[i];
            a[i] = a[index_min];
            a[index_min] = temp;
        }
    }
    end_time = clock();
    time_passed = (double)(end_time - start_time)/CLOCKS_PER_SEC;
    //return time_passed;
    printf("\nTime: %lf",time_passed);
    printf("\nSwap count: %ld",swap_count);
    printf("\nComp count: %ld\n",comp_count);
}

void insertion_sort(int a[], int n)
{
    int i, j, item;
    long comp_count = 0;
    clock_t start_time, end_time;
    double time_passed;

    start_time = clock();
    for(i=1; i<n; i++)
    {
        item = a[i];
        j = i-1;
        comp_count++;
        while(j>=0 && a[j]>item)
        {
            swap_count++;
            a[j+1] = a[j];
            j = j-1;
        }
        a[j+1] = item;
    }
    end_time = clock();
    time_passed = (double)(end_time - start_time)/CLOCKS_PER_SEC;
    //return time_passed;
    printf("\nTime: %lf",time_passed);
    printf("\nSwap count: %ld",swap_count);
    printf("\nComp count: %ld\n",comp_count);
}


int main()
{
    int num;
    int  i, j, digit;
    double selection, bubble, insersion;

    printf("Enter number range:  ");
    scanf("%d",&num);

    printf("Enter a number to fix digit range:  ");
    scanf("%d",&digit);

    srand(time(0));

    for(i=0; i<num; i++)
    {
        array[i] = rand() % digit + 1;
    }

    printf("\nFor bubble sort : ");
    bubble_sort(array, num);
    printf("\nFor selection sort : ");
    selection_sort(array, num);
    printf("\nFor insertion sort : ");
    insertion_sort(array, num);

}