Need help on insertion sort problem

See more:

C++

algorithm

Been stuck on this problem for about a week. Comes from the Introduction to Algorithms textbook.

My problem is im not sure if my solution is correct and the visual studio compiler doesnt compile correctly, stating that int data[n]; needs to be a constant


Code the insertion sort in C++. Create 2 .cpp files: sortMain.cpp and insertionSort.cpp. Below is a template that you must use.

<pre>    //----------------------------------------------------------------------
    //file: sortMain.cpp
    #include < iostream >

    extern void insertionSort ( int A[], int n );

    using namespace std;

    int main ( int argc, char* argv[] ) {
        .
        .
        .
        return 0;
    }


    //----------------------------------------------------------------------
    //file: insertionSort.cpp
    void insertionSort ( int A[], int n ) {
        .
        .
        .
    }

Run the sort on input sizes of 10, 100, 1000, 10000, 100000, 200000, 300000, 400000, 500000, and 1000000 of random values. Depending upon the speed of your computer, you may only be able to run one or a few sorts for larger input sizes. On the other hand, for small array sizes, you may have to repeatedly call insertion sort to get good statistics (try to get a total elapsed or total CPU times of at least 15 seconds by increased the number of repeats, #, in the table). Report the array size n (N), number of test iterations (#) necessary to get good stats, total elapsed time (tElapsed), total CPU time (tCPU), average CPU time (avgCPU) for insertion sort in a table like below.

Note: You may need to allocate your arrays dynamically as follows, int* A = new int[ N ]; rather than statically as in int A[ N ];. Then you can refer to individual array elements as usual (A[0], ..., A[N-1]). (Don't forget to delete A when finished.)


N # tElapsed tCPU avgCPU
10
100
1000
10000
100000
200000
300000
400000
500000
1000000


A note about random number generation:
/*
* rand() is not a very good random number generator (avoid use).
* random() is good but not available on winows.
* best to use mt19937.
*/

#include < iostream >
#include < random >

using namespace std; int main ( int argc, char* argv[] ) { /* srand( (unsigned int)time( NULL ) ); for (int i=0; i<10; i++) { cout << rand() << endl; } */ //based on: https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution mt19937 gen( (unsigned int)time(NULL) ); //Standard mersenne_twister_engine seeded with time uniform_int_distribution<> distrib( 1, 10000 ); for (int i=0; i<10; ++i) { //Use `distrib` to transform the random unsigned int generated by gen into an int in [1, 6] cout << distrib( gen ) << endl; } return 0; }

What I have tried:

<pre>#include <iostream>
#include <stdlib.h>

#include <time.h>
using namespace std;


void insertionSort(int array[], int size) {
  for (int step = 1; step < size; step++) {
    int key = array[step];
    int j = step - 1;

    while (key < array[j] && j >= 0) {
      array[j + 1] = array[j];
      --j;
    }
    array[j + 1] = key;
  }
}

//driver code
int main() {
  
  
  
  
   for(int n=10;n<=1000000;n=n*10){    
    int data[n];
   for(int i = 0 ; i < n ; i++ ) {
      data[i]= rand() % 1000;
   }
   clock_t tStart = clock();
   insertionSort(data, n);
   cout<<n<<" size time is: "<< (double)(clock() - tStart)/CLOCKS_PER_SEC<<endl;
    
   }

}