Seg Fault, possible array pointer issue (Radix Sort Implementation)

Question

I am attempting to do a Radix sort on an array of "random" integers. The radix_sort function is giving me seg fault errors. I checked each for loop and none of them seem to go out of bounds so my assumption is that the problem may be the array pointers but I couldn't seem to find any source information on the web that helped with any such issue. Compiled with GCC with -std=c99 flag

#include <stdio.h>
#include <stdlib.h>

#define LEN 1000
#define BYTES 4
#define BINS 256

void create_lst();
void int_radix_sort();
void radix_sort(int);

long data[LEN];
long temp[LEN];

int main(int argc, char * * argv) {
  create_lst();
  int_radix_sort();

  return 0;
}
void create_lst() {
  for (int i = 0; i < LEN; i++) {
    srand(rand());
    data[i] = rand();
  }
  return;
}
void int_radix_sort() {
  for (int i = 0; i < BYTES; i++) {
    radix_sort(i);
  }
  return;
}
void radix_sort(int byte) {
  long map[BINS], count[BINS];
  long *src_p, *dst_p;

  if((byte%2) == 0){
    src_p = data;
    dst_p = temp; 
  } else {
    src_p = temp;
    dst_p = data;
  }
  // Count
  for(int i = 0; i < LEN; i++)
    count[(src_p[i] >> (byte*8)) & (BINS-1)]++;
  // Map
  map[0]=0;
  for(int j = 1; j < BINS; j++)
    map[j] = count[j-1] + count[j-1];
  // Move
  for(int k = 0; k < LEN; k++)
    dst_p[map[(src_p[k] >> (byte*8)) & (BINS-1)]++] = src_p[k];
  return;
}

Edit: More info - When I ran the program through a debugger I found the issue was on the last loop (with K variable)

srand(rand()) isn't going to seed your random number generator usefully. — Carl Norum
– Carl Norum, Commented May 27, 2013 at 16:39
When I ran the program through a debugger I found the issue was on the last loop (with K variable) — Mike
– Mike, Commented May 27, 2013 at 16:46

Bryan Olivier · Accepted Answer · 2013-05-27 16:58:18Z

3

The count array in radix_sort is uninitialized and its values are used for creating values in map, which in the end (see // Move) is used to index dst_p and then it is BOOM.

After your fix to initialize them, you end up with 1954 in map[1], which is too big for dst_p, so now you are looking at an algorithmic problem. Try to add some tracing print statements to tackle your problem. Or go into a debugger (gdb on Linux) and step through your program to verify that all steps are as expected.

edited May 27, 2013 at 16:58

answered May 27, 2013 at 16:48

Bryan Olivier

5,3472 gold badges19 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mike Over a year ago

I just tried changing the initialization of count and map to "long map[BINS] = {0}, count[BINS] = {0};" but it still is giving me seg faults, am I doing it incorrectly?

Daniel Fischer · Accepted Answer · 2013-05-27 17:37:22Z

1

for(int j = 1; j < BINS; j++)
    map[j] = count[j-1] + count[j-1];

is wrong. You want map[j] to hold the cumulative number of elements in the previous slots, so that ought to be

for(int j = 1; j < BINS; j++)
    map[j] = map[j-1] + count[j-1];
         //  ^^^
         //  add the number of items in bin j-1 to the number of items in previous bins

answered May 27, 2013 at 17:37

Daniel Fischer

184k19 gold badges319 silver badges436 bronze badges

1 Comment

Mike Over a year ago

Thank you, that was such a silly error. Sometimes you need a second pair of eyes looking at a code(or maybe some more time in the debugger).

Collectives™ on Stack Overflow

Seg Fault, possible array pointer issue (Radix Sort Implementation)

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related