0

This question is not about where to put the srand function.

I have just started learning DSA with Insertion Sort. I have written a C++ program to perform Insertion Sort and wanted to create some neat visuals of the Time Analysis. I tried generating Random Arrays for the Time Analysis using the rand() function but the Arrays generated seem to have a character at the end. The elements in the character array should all be single digit integers like '0' '3' and so on.....

The Main Function of the Program:

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <iomanip>

using namespace std;

int size(char a[]) {
    int l = 0;
    while (a[l] != NULL) {
        l++;
    }
    return l;
}

void InsertionSort(char arr[]) {

    for (int k = 1; k < size(arr); k++) {
        char temp = arr[k];
        int i = k - 1;
        while (i >= 0 && arr[i] > temp) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = temp;

    }
}

int main(void) {

    //Generate Random Arrays of size snum
    for (int k = 1; k < 100; k++) {

        int snum = k * 100;
        char Array[snum];
        srand(time(NULL));
        for (int s = 0; s < snum; s++)
        {
            int no = rand() % 9 + 1;
            Array[s] = no + '0';
        }

        cout << "START\t";
        //cout<<"\n"<<Array<<"END\n"; // Character is being Printed at the end........ :-(
        clock_t start, end;
        start = clock();

        InsertionSort(Array);
        end = clock();
        double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
        cout << "\"" << fixed << time_taken << setprecision(9) << "\",\"" << 100 * k << "\"" << endl;
    }
}

How I Compile and Run the Program:

g++ InsertionSort.cpp 
./a.out > InsertionSort.txt

--------------EDIT--------------

Based on the suggestions, I have replaced the Array with a vector. Please provide any further suggestions....

RandomIntVector.cpp

#include "RandomIntVector.h"
#include <random>
#include <vector>

using namespace std;

vector<int> RandomVector(int size){

uniform_int_distribution<> d(1, 1000);
mt19937 gen;

vector<int> Ar;
for(int s=0; s<(size-1); s++)

    {

        int no = d(gen);

        Ar.push_back(no);

    }

return Ar;}

InsertionSort.cpp

#include "InsertionSort.h"
#include <vector>
using namespace std;

void InsertionSort(vector<int> arr){


int size=arr.size();
for(int k=1;k<size;k++){
    int temp = arr[k];
    int i=k-1;
    while(i>=0 && arr[i]>temp ){
        arr[i+1]=arr[i];
        i--;
    }
    arr[i+1]=temp;
    
}

}

Main.cpp

#include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>
#include "RandomIntVector.h"
#include "InsertionSort.h"

using namespace std;



int main(void){

//Generate Random Arrays of size snum

for(int k=1;k<100;k++){    

    vector<int> Array = RandomVector(100*k);


    clock_t start, end;


    start = clock();

    InsertionSort(Array);
    
    end = clock();

    double time_taken = double(end - start) / 
    double(CLOCKS_PER_SEC);

    
    //Print the Time Taken along with the size of the Input

    cout<<"\""<<fixed << time_taken << setprecision(9)<<"\",\"" 
 <<100*k<<"\""<<endl;


}


return 0;
}
Prad
  • 47
  • 8
  • 1
    Do you know what `srand` does? You do not want to call it inside a loop. Why use `rand` at all when there is modern c++ ``? – Quimby Nov 21 '22 at 18:53
  • @Quimby I am having some problem in the Array itself. A character is there at the end of the Array....... – Prad Nov 21 '22 at 18:57
  • @Quimby Thanks. I will use from now onwards. I used rand only because many online tutorials used the same. – Prad Nov 21 '22 at 19:01
  • 2
    Neither the question nor the problem are related to the mentioned dupe. The problem is with using VLA (Variable Length Arrays), like in `char Array[snum];` This is not allowed in C++. Please use a `std::vector` instead. – A M Nov 21 '22 at 20:00
  • 1
    `while (a[l] != NULL)`: 'NULL' is a pointer, not an integer constant. It **might** be implemented in C++ as a simple '0', but that is by no means guaranteed. – Pete Becker Nov 21 '22 at 21:29
  • Wait, your `InsertionSort` function takes an array of `int` but you're calling it with an array of `char`? That can't possibly work, and it shouldn't even compile. – Pete Becker Nov 21 '22 at 21:32
  • 1
    @Prad -- there's nothing wrong with using `srand()` and `rand()` when you're getting code up and running. The new random stuff is much more sophisticated, sure, but it's more complex to get started with. – Pete Becker Nov 21 '22 at 21:35
  • @PeteBecker ahh I'm sorry. I had tried the program for both int and char arrays and while Editing the question I didn't change the InsertionSort Function. – Prad Nov 22 '22 at 07:09
  • The problem is that Array is assumed to be NUL-terminated, but isn't. That will make size misbehave and printing to print extra characters. Use a std::vector or make room for it with: char Array[snum+1]; Array[snum]=0; – Hans Olsson Nov 22 '22 at 08:15
  • I have incorporated the suggestions. Many thanks for all the help. – Prad Nov 22 '22 at 10:56
  • In the revised version that uses `mt19937`, by constructing a new engine in each call of `RandomVector`, you get the same vector everytime because you always get the same sequence of random numbers. That may be the purpose, but most likely it is not, right? – j6t Nov 22 '22 at 11:16
  • @j6t No it's not. But it's enough I guess for my purpose. – Prad Nov 22 '22 at 11:37
  • @Prad -- to clarify my earlier comment about `NULL`, don't confuse it with the nul character; the names sound alike, and they perform similar roles, but they are not the same thing. The nul character is simply `'\0'`. If you're looking for it, just use it: `while (a[l] != '\0\)...`. `NULL` is a macro that expands to a null (note: two ells) pointer constant. In C it usually expands to `(void*)0`. That doesn't work in C++ because `void*` doesn't get promoted to other pointer types. In the olden days of C++ it simply expanded to '0', which has the same **value** as `'\0'`, so it sometimes works. – Pete Becker Nov 22 '22 at 14:24
  • @Prad (continuing) -- But many compilers today expand `NULL` to `nullptr`, a keyword for a null pointer constant that (unlike `(void*)0`) can be converted to any pointer type. `nullptr` is not an integral constant, so comparisons with integer values don't make sense to the compiler. Comparing non-pointer types to `NULL` never really made sense, because they're fundamentally different types, but now there's a mechanism to prevent it from being done. – Pete Becker Nov 22 '22 at 14:28

0 Answers0