Click here to Skip to main content
15,399,959 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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.

C++
<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:

C++
<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;
    
   }

}
Posted
Updated 4-Feb-22 6:45am
v2
Comments
Richard MacCutchan 4-Feb-22 12:03pm
   
Very interesting, but do you have a question?
Tre Seibert 4-Feb-22 12:04pm
   
Yes my code doenst work properly and Im not sure why. Im also looking for clarification that my code is correct.
Richard MacCutchan 4-Feb-22 12:11pm
   
Telling us that it doesn't work, is not helpful. You need to explain exactly what the problem is and where it occurs.
Tre Seibert 4-Feb-22 12:19pm
   
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
jeron1 4-Feb-22 12:44pm
   
'n' needs to be known at compile time, in your case it is not. There are ways to deal with this through dynamic allocation. But first, what are you trying to achieve with the 2 for loops?
Richard MacCutchan 4-Feb-22 12:48pm
   
Sorry that message was not meant for you.
jeron1 4-Feb-22 13:02pm
   
No problem. :)
Richard MacCutchan 4-Feb-22 12:49pm
   
See my solution below.

1 solution

You cannot allocate an array in that way, and even if you could you will soon run out of memory. You need to use the new and delete operators to manage your arrays thus:
C++
for(int n=10;n<=1000000;n=n*10){
    int* data = new int[n]; // allocate a new array for the numbers
    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;
    delete[] data; // delete the array ready for the next allocation.
}

These changes should at least get you a clean build.
   
v2
Comments
Tre Seibert 4-Feb-22 12:56pm
   
Thank you! Do you have any idea on how to calculate the total CPU time?
Rick York 4-Feb-22 13:08pm
   
This can help : https://www.codeproject.com/Tips/5254574/High-Resolution-Timing

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900