Memory problems

[Debaser]

Could someone point out the error in the following code. It fails on
the last line.

double counting_sort(long* input, long inSize)
{
time_t start, end;
long x, k = 0, count = 0;
long *b, *c;

/* Get size of c array */
for (x = 0; x < inSize; x++) {
if (k < input[x]) {
k = input[x];
}
}

/* Allocate sorted array */
b = new long[inSize];
if (!b) {
cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

/* Allocate storage array */
c = new long[k+1];
if (!c) {
cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

time(&start);

/* init c */
for (x = 0; x <= k; x++) {
c[x] = 0;
}

/* count elements equal to x */

for (x = 0; x < inSize; x++) {
c[input[x]]++;
}

.....


It crashes on the first interation of the last for loop. I'm sure it's
just some stupid oversight between pointers and values, but I can't
figure it out.

Thanks in advance.

-Mike-

 

[Victor Bazarov]

Could someone point out the error in the following code. It fails on
the last line.

double counting_sort(long* input, long inSize)
{
time_t start, end;
long x, k = 0, count = 0;
long *b, *c;

/* Get size of c array */
for (x = 0; x < inSize; x++) {
if (k < input[x]) {
k = input[x];
}
}

So, 'k' is the maximum of all 'input' values. OK.

/* Allocate sorted array */
b = new long[inSize];
if (!b) {
cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

You can safely drop the 'if' statement. 'new' does not return NULL if
no more memory left. 'new' throws the 'std::bad_alloc' exception.

/* Allocate storage array */
c = new long[k+1];
if (!c) {
cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

Same here. Just remove the 'if', unclog your code.

time(&start);

/* init c */
for (x = 0; x <= k; x++) {
c[x] = 0;
}

/* count elements equal to x */

for (x = 0; x < inSize; x++) {
c[input[x]]++;
}

....


It crashes on the first interation of the last for loop. I'm sure it's
just some stupid oversight between pointers and values, but I can't
figure it out.

Nothing in _this_ code is wrong. Could it be that one of your 'input'
values (the first one) is actually negative?

V

 

[=?iso-8859-1?Q?Ali_=C7ehreli?=]

Could someone point out the error in the following code. It fails on
the last line.

double counting_sort(long* input, long inSize)
{
time_t start, end;
long x, k = 0, count = 0;
long *b, *c;

These names are too short to make the code readable. Please pick more
descriptive names.

/* Get size of c array */
for (x = 0; x < inSize; x++) {
if (k < input[x]) {
k = input[x];
}
}

/* Allocate sorted array */
b = new long[inSize];
if (!b) {

new never returns 0. Please read about std::bad_alloc.

cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

/* Allocate storage array */
c = new long[k+1];
if (!c) {

Same here...

cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

time(&start);

/* init c */
for (x = 0; x <= k; x++) {
c[x] = 0;
}

/* count elements equal to x */

for (x = 0; x < inSize; x++) {

You are assuming that input[x] can be used as an array index below. Make
that assumption explicit:

assert((input[x] >= 0) && (input[x] <= k));

It may show you the error.

c[input[x]]++;
}

....


It crashes on the first interation of the last for loop. I'm sure it's
just some stupid oversight between pointers and values, but I can't
figure it out.

Ali

 

[Debaser]

You were right. I was sending in corrupt input. The assert caught it,
as expected, but the parent function was using the wrong loop index to
fill input[]. Funny though that there are 4 other sorting algorithms
above it that had no problems.

Thanks so much!

-Mike-

 

[Peter Koch Larsen]

Could someone point out the error in the following code. It fails on
the last line.

double counting_sort(long* input, long inSize)
{
time_t start, end;
long x, k = 0, count = 0;
long *b, *c;

/* Get size of c array */
for (x = 0; x < inSize; x++) {
if (k < input[x]) {
k = input[x];
}
}

/* Allocate sorted array */
b = new long[inSize];

Most of your problems are related to your use of pointers. Just don't use
them and use the standard library (in your case std::vector).

/Peter

if (!b) {
cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

/* Allocate storage array */
c = new long[k+1];
if (!c) {
cerr << "Out of memory.\n";
exit(EXIT_FAILURE);
}

time(&start);

/* init c */
for (x = 0; x <= k; x++) {
c[x] = 0;
}

/* count elements equal to x */

for (x = 0; x < inSize; x++) {
c[input[x]]++;
}

....


It crashes on the first interation of the last for loop. I'm sure it's
just some stupid oversight between pointers and values, but I can't
figure it out.

Thanks in advance.

-Mike-