Write a program to sort a given set of elements using the insertion sort.

Write a program to sort a given set of elements using the insertion sort. Additionally, determine the time required (in terms of steps) to sort the elements.

(Note: assume cost of any basic operation is 1, i.e., c1

= c2 = ... = c8 = 1).

1) Repeat the experiment for different values of n = 500, 1000,

5000, 10000

2) For each of aforementioned case, consider arrays as random,

sorted, and reverse-sorted. Provide the complexity in terms of

step count.

Note: No keyboard input. Use Random number generator

Help: Random Number Generator

Random Number Generation

#include <stdlib.h>

#include <time.h>

srand(time(NULL)); //once

rand()%30; //everytime

Generating in sorted order

arr[0] = rand()%100;

//for sorted order

for(int i = 1; i < arr_size; i++){

arr[i] = arr[i - 1] + rand()%30;

}

Code 

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

int i, j;

int *fill(int n)
{

    int *arr;
    arr = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
        arr[i] = rand() % 10000;
    return arr;
}

int insertionSort(int arr[], int n)
{
    int i, key, j, count = 0;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
            count += 2;
        }
        arr[j + 1] = key;
        count++;
    }
    return count + 1;
}
int main()
{
    int steps_random, steps_sorted, steps_reverse;
    int a = 0, b = 0, c = 0;

    for (j = 0; j < 500; j++)
    {
        int *arr = fill(200);
        int *random = fill(200);

        steps_sorted = insertionSort(arr, 200);
        steps_random = insertionSort(random, 200);

        int rev[200];
        for (i = 0; i < 200; i++)
        {
            rev[i] = arr[200 - 1 - i];
        }
        steps_reverse = insertionSort(rev, 200);

        a += steps_random;
        b += steps_sorted;
        c += steps_reverse;
    }

    printf("\nFOR 500 ITERATION OF 200 SIZE ARRAY STEP COUNT ARE");
    printf("\n\tsorted : %d\n\trandom : %d\n\treverse : %d\n\t", b / 500, a / 500, c / 500);

    for (j = 0; j < 1000; j++)
    {
        int *arr = fill(200);
        int *random = fill(200);

        steps_sorted = insertionSort(arr, 200);
        steps_random = insertionSort(random, 200);

        int rev[200];
        for (i = 0; i < 200; i++)
        {
            rev[i] = arr[200 - 1 - i];
        }
        steps_reverse = insertionSort(rev, 200);

        a += steps_random;
        b += steps_sorted;
        c += steps_reverse;
    }

    printf("\nFOR 1000 ITERATION OF 200 SIZE ARRAY STEP COUNT ARE");
    printf("\n\tsorted : %d\n\trandom : %d\n\treverse : %d\n\t", b / 1000, a / 1000, c / 1000);

    for (j = 0; j < 10000; j++)
    {
        int *arr = fill(200);
        int *random = fill(200);

        steps_sorted = insertionSort(arr, 200);
        steps_random = insertionSort(random, 200);

        int rev[200];
        for (i = 0; i < 200; i++)
        {
            rev[i] = arr[200 - 1 - i];
        }
        steps_reverse = insertionSort(rev, 200);

        a += steps_random;
        b += steps_sorted;
        c += steps_reverse;
    }

    printf("\nFOR 10000 ITERATION OF 200 SIZE ARRAY STEP COUNT ARE");
    printf("\n\tsorted : %d\n\trandom : %d\n\treverse : %d\n\t", b / 10000, a / 10000, c / 10000);
}

Output

FOR 500 ITERATION OF 200 SIZE ARRAY STEP COUNT ARE

        sorted : 20063

        random : 20122

        reverse : 39995

FOR 1000 ITERATION OF 200 SIZE ARRAY STEP COUNT ARE

        sorted : 30163

        random : 30212

        reverse : 59993

FOR 10000 ITERATION OF 200 SIZE ARRAY STEP COUNT ARE

        sorted : 23110

        random : 23116

        reverse : 45995