Bubble sort vs Insertion sort run-time

Question

I'm trying to write a program that calculates the run-time of a bubble sort vs an insertion sort. It takes in two inputs, number of elements and elements, and calculates their run-time. This is what I have so far, but it is printing the same time for both sorters.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

int bubblesort(int a[], int n);
int insertionsort(int a[], int n);

int main()
{
    int s,temp,i,j,comparisons,a[20];
    float function_time;
    clock_t start;
    clock_t end;
    printf("Enter total numbers of elements: ");
    scanf("%d",&s);
    printf("Enter %d elements: ",s);

    for(i=0;i<s;i++)
    scanf("%d",&a[i]);

  //Bubble sorting algorithm

    for(i=s-2;i>=0;i--)
    {
        for(j=0;j<=i;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];

                a[j]=a[j+1];

                a[j+1]=temp;
            }
        }
    }

    for(i=0;i<s;i++)
    a[i]= rand()%10000;

    start = clock();    
    comparisons= bubblesort(a, s);
    end = clock();
    function_time = (float)(end)/(CLOCKS_PER_SEC);  // Time in seconds
    printf("\nTime for Bubble Sort is %f microseconds\n ", function_time);

    // Insertion sorting algorithm

    for(i=1;i<s;i++)
    {
        temp=a[i];
        j=i-1;
        while((temp<a[j])&&(j>=0))
        {
            a[j+1]=a[j];
            j=j-1;
        }
        a[j+1]=temp;
    }

    for(i=0;i<s;i++)
    a[i]= rand()%10000;

    start = clock();    
    comparisons= insertionsort(a, s);
    end = clock();
    function_time = (float)(end)/(CLOCKS_PER_SEC);  // Time in seconds
    printf("\nTime for Insertion Sort is %f microseconds\n ", function_time);

    return 0;
}

int bubblesort(int a[], int n)
{
    bool swapped = false;
    int temp=0, counter=0;

    for (int j = n-1; j>0; j--)
    {
        swapped = false;
        for (int k = 0; k<j; k++) 
            {
                counter++;
                if (a[k+1] < a[k]) 
                {
                    temp= a[k];
                    a[k] = a[k+1];
                    a[k+1]= temp;
                    swapped = true;
                }
            }
        if (!swapped)
            break;
    }

return counter;
}

int insertionsort(int a[], int n)
{
    bool swapped = false;
    int temp=0, counter=0;
    for (int i=1; i<=n; i++)
    {    
        for (int s=i; s>0; s--)
        {
            counter++;
            if (a[s]<a[s-1])
            {
                temp=a[s-1];
                a[s-1]=a[s];
                a[s]=temp;
                swapped = true;
            } 
        }
        if (!swapped)
            break;
    }
return counter;
}

Answer 1

Firstly, the way you calculate the sorting time is wrong:

function_time = (float)(end)/(CLOCKS_PER_SEC);

It should be:

function_time = (float)(end-start)/(CLOCKS_PER_SEC);

Secondly, although bubble sort and insertion sort both have O(n square) complexity, time taken should have some difference, they cannot be the same. If the problem persists, you should check the output of clock() function, it may not work in your system.

Edit: I found that your code let user type in the elements manually. So I guess your array can only be relatively small. Sorting small-size array takes very little time so the difference is hard to notice. You should let the elements assigned randomly by code, so that you can generate large array for analysis.