Reagan Weatherly - 11 months ago 47

C++ Question

I've got this really strange problem when trying to use this code for implementing a group quick select algorithm. I use a 2D dynamically allocated array to hold the individual elements in groups of the randomly generated unsorted array of 10 numbers. When I run the code with a group size of 2, 5, or 10 it works perfectly. But when I change the group size to a number that would leave one group smaller than the others, it breaks when I try to initialize the contents of the array to some test figures. Thanks for any advice.

`#include <iostream>`

#include <cstdlib>

#include <ctime>

#include <random>

#include <array>

using namespace std;

int groupSize = 0;

int groupSelect(int *, int, int, int);

int main()

{

// randomize array of size 10 with entries between 1 and 20.

random_device rd;

mt19937 eng(rd());

uniform_int_distribution<> distr(1, 20);

int max = 10;

int * Array;

Array = new int[max];

for (int i = 0; i < max; i++)

{

Array[i] = distr(eng);

}

// display array contents (unsorted)

cout << "Array contents are:\n";

for (int i = 0; i < max; i++)

{

cout << Array[i] << ", ";

}

cout << endl;

/*------------------------------------------------------------------------------*/

groupSize = 3;

int poo = groupSelect(Array, 0, 9, 5);

return 0;

/*------------------------------------------------------------------------------*/

delete[] Array;

}

int groupSelect(int* arr, int start, int end, int k)

{

bool remainder = false;

int size = 10;

if ((size % groupSize) != 0)

{

remainder = true;

}

//size = amount of groups of 5 (and remainder group)

size = size - (size % groupSize);

size = size / groupSize;

if(remainder)

size++;

cout << "Size = " << size << endl;

int** groups = new int*[size];

for (int i = 0; i < size; ++i)

{

if (remainder == true)

{

if (size - i == 1)

groups[i] = new int[((size) % (groupSize))];

}

else

groups[i] = new int[groupSize];

}

int testV = 0;

for (int i = 0; i < size; i++)

{

int temp = groupSize;

if (size - i == 1)

{

if (remainder)

temp = size % groupSize;

}

for (int j = 0; j < temp; j++)

{

groups[i][j] = testV; // codes break here

testV++;

}

}

cout << "\nGroup arrays' contents\n" << endl;

for (int i = 0; i < size; i++)

{

for (int j = 0; j < groupSize; j++)

{

cout << "groups[" << i << "]["<<j<<"] contents = " << groups[i][j] << endl;

}

}

delete[] groups;

return 0;

}

Answer Source

You have a bug in this piece: if remainder is true but size - 1 != 1 you would never initialize your arrays and then you trying to access them

```
for (int i = 0; i < size; ++i)
{
if (remainder == true)
{
if (size - i == 1)
groups[i] = new int[((size) % (groupSize))];
}
else
groups[i] = new int[groupSize];
}
```