Counting sort segmentation fault in C

Question

Below is my attempt at a counting sort. I have diagrammed my logic, run through it verbally, and commented my code thoroughly. However, my code causes a segmentation fault. I understand a segmentation fault represents an illegal access to memory, so this must mean one of my index values is trying to access an index outside of an array's range. However, I can't figure out why this is happening.

Fortunately, my debugger highlights the line below, which I've also noted in a comment, where the segmentation fault occurs. Nevertheless, I am entirely stumped. Would appreciate any help understanding the nature of this segmentation fault, thank you.

void sort(int values[], int n)
{

    //create array of finite size (65536)
    int countArray[INT_MAX];

    //create array to eventually store sorted values
    int sortedValues[n];

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }


    //starting index for sortedValues[]
    int sortedIndex = 0;

    //loop until we've reached the end of sortedValues[]
    while(sortedIndex < n) {

        //loop through each index value of countArray
        //j represents the value
        for(int j = 0; j < INT_MAX; j++) {

            //how many times does the index of countArray occur in values[]?
            int c = countArray[j];

            //only add index j as a value to sortedValues[] if it appears in values[]
            while(c > 0) {

                //append j to sortedValues[]
                //--SEGMENTATION FAULT OCCURS ON THE LINE BELOW--
                sortedValues[sortedIndex] = j;

                //decrease the count of countArray[j] once value appended to sortedValues[]
                c -= 1;

                //move to next index of sortedValues[]
                sortedIndex += 1;
            }
        } 
    }
    return;
}

Check out the scope of some of the arrays based on where you've declared them. — nfproductions
– nfproductions, Commented May 4, 2017 at 3:19
You never initialised countArray. This can cause c to be anything. Which can cause sortedIndex to go to any value (including negative) — Ajay Brahmakshatriya
– Ajay Brahmakshatriya, Commented May 4, 2017 at 3:20
@BradBales OP probably means that the data passed into his function does not exceed 2^16. I thought the same thing when I saw this line, but then I thought that 16-bit ints are both negative and positive, so the logic is going to break. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented May 4, 2017 at 3:27
@BradBales 16-bit int is common in embedded processors. 100s million per year in 2016 — chux
– chux, Commented May 4, 2017 at 3:42

Sergey Kalinichenko · Accepted Answer · 2017-05-04 03:23:27Z

5

You need to initialize countArray elements to zero to fix the crash:

int countArray[INT_MAX] = {0};

However, your function is still useless, because it places sorted numbers into a local array that never makes it out of the function. In order to fix this, remove sortedValues array, and use the original values array for the output instead:

values[sortedIndex] = j;

Now the caller will see that the array he passed into your function comes back sorted.

Note: The outer loop while(sortedIndex < n) is harmless but useless, because the for loop guarantees that sortedIndex is exactly n. You should remove the while loop from your code.

answered May 4, 2017 at 3:23

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

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

Comments

Ahmed Akhtar · Accepted Answer · 2017-05-04 03:52:42Z

As I have commented earlier you don't need a separate loop for sortedIndex.

And as suggested by @dasblinkenlight you don't need to create a local array sortedValue to store the sorted values instead you can sort the array values in place.

Also, you need to initialize countArray with all zeros to avoid garbage values to be indexed.

Here is the code:

void sort(int values[], int n)
{
    //create array of finite size (65536)
    int countArray[INT_MAX] = {0};

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }

    //starting index for sortedValues[]
    int sortedIndex = 0;

   //loop through each index value of countArray
   //j represents the value
   for(int j = 0; j < INT_MAX; j++) {

    //how many times does the index of countArray occur in values[]?
    int c = countArray[j];

    //only add index j as a value to sortedValues[] if it appears in values[]
    while(c > 0) {
     //append j to sortedValues[]
     values[sortedIndex] = j;

     //decrease the count of countArray[j] once value appended to sortedValues[]
     c -= 1;

     //move to next index of sortedValues[]
     sortedIndex += 1;
    }
   }
}

Collectives™ on Stack Overflow

Counting sort segmentation fault in C

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related