#include <iostream>

using namespace std;

//Functions
int add(int Arr[], int limit);
int sort(int Arr[],int length);



int main()
{
//Initialize Variables
srand((unsigned)time(NULL));

int n;

n = 100;
int Arr1[n];

add(Arr1,n);
cout << n << "              " << sort(Arr1,n)<<endl;


n = 500;
int Arr2[n];

add(Arr2,n);
cout << n << "              " << sort(Arr2,n)<<endl;

n = 1000;
int Arr3[n];

add(Arr3,n);
cout << n << "              " << sort(Arr3,n)<<endl;

n = 5000;
int Arr4[n];

add(Arr4,n);
cout << n << "              " << sort(Arr4,n)<<endl;

n = 10000;
int Arr5[n];

add(Arr5,n);
cout << n << "              " << sort(Arr5,n)<<endl;

n = 25000;
int Arr6[n];

add(Arr6,n);
cout << n << "              " << sort(Arr6,n)<<endl;

n = 50000;
int Arr7[n];

add(Arr7,n);

cout << n << "              " << sort(Arr7,n)<<endl;

n = 75000;
int Arr8[n];

add(Arr8,n);
cout << n << "              " << sort(Arr8,n)<<endl;

n = 100000;
int Arr9[n];

add(Arr9,n);
cout << n << "              " << sort(Arr9,n)<<endl;

system("PAUSE");
}
//Adds the random numbers to the array
int add(int Arr[], int limit)
{
int num;
int i;
for(i = 0; i < limit; i++)
    {
        num = rand()%49999;
        Arr[i] = num;
    }
    return i;
    }

//Sorts the array,insertion sort
int sort(int Arr[],int len)
    {
    int count=0;
    int a, i;
    for(int j = 1; j < len; j++)
    {
        a = Arr[j];
        count++;
        i = j - 1;

         while(Arr[i] > a && i >= 0)
         {
         count++;
         Arr[i + 1] = Arr[i];
         i--;
         }

    count++;
    Arr[i + 1] = a;
    count++;
    }
 return count;
}