creating a small sort (introduction to c++ class)

Question

I am currently a college student taking a introduction for c++ class and I got stuck on this problem. "Define a function

void smallSort(int nums[], int length)

that uses the "small sort" algorithm to sort a sequence of small numbers. (In our case "small" means anything between 0 and 9999.) The algorithm works as follows: Declare a local int array called counts of size 10000 and initialize each element to 0. Then loop through the array nums and for each number, increment the element of counts with that index. The last step is to loop through the counts array and copy back values into nums. For example if your loop is currently at element 3 of the counts array and counts[3] contains a 10, you would copy ten 3's into the nums array.

As an example: suppose nums is { 1, 4, 3, 0, 0, 4, 1, 4, 1, 2, 6, 4, 6, 0, 0, 0, 0, 4} and length is 18. Then after filling the counts array, it would contain the values {6, 3, 1, 1, 5, 0, 2, ... }, with all elements after counts[6] equal to 0. That's because the array nums contains six 0's, three 1's, one 2, one 3, five 4's zero 5's, two 6's and no values bigger than 6. In the next phase of the algorithm we'll loop through the counts array and copy back six 0's, then three 1's, one 2 etc. into the nums array so it contains {0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6}. Notice that nums is now sorted in ascending order."

This is my solution:

void smallSort(int nums[], int length){
int count [10000];
    int a = 0;
    for(int i =0; i<10000; i++){
        count[i] = 0;
    }
    for(int i =0; i<length ; i++){
    count[nums[i]]++;   
    }
    for(int i = 0; i< length; i++){
        for(int j = 0; j<count[i]; j++){
            nums[a] = count[i];
            a++;
        }
    }
}

This is the answer I am supposed to get: 0·1210·3000·2434·446·54·111·900·43·7·17·1001·9999·0·0·9999·1210·54↵ 0·0·0·7·17·43·54·54·111·446·900·1001·1210·1210·2434·3000·9999·9999·↵

And this is what I am getting: 0·1210·3000·2434·446·54·111·900·43·7·17·1001·9999·0·0·9999·1210·54·↵ 3·3·3·1·1·54·111·900·43·7·17·1001·9999·0·0·9999·1210·54·↵

I have bene trying to solve this problem for over 2h and since I kept getting the problem wrong I decided to create my own array on Xcode and try to solve it but an error appears next to "count[nums[i]]++;" which says, "Thread 1: EXC_BAD_ACCESS (code=1, address=0x7ffeefc15928)".

Answer 1

There are a couple of issues with your smallsort function.

1. The count array contains the frequencies of each value of the input. And you are assigning the frequency to nums[a].

2. The outer for loop (where nums array is being refilled) has to iterate through all of the count array because the input values can be anywhere between 0 and 9999.

With these modifications the code will look like this:

void smallSort(int nums[], int length){
    int count [10000] = {0}; //This will set all array elements to 0
    int a = 0;

    for(int i =0; i<length ; i++){
        count[nums[i]]++;   
    }
    for(int i = 0; i< 10000; i++){
        for(int j = 0; j<count[i]; j++){
            nums[a] = i;
            a++;
        }
    }
}

int main(int argc, char const *argv[])
{
    int nums[] = {0, 1210, 3000,2434,446,54,111,900,43,7,17,1001,9999,0,0,9999,1210,54};
    smallSort(nums, 18);

    for(auto& i: nums)
        cout << i << ' ';       

    return 0;
}

Output:

a.exe
0 0 0 7 17 43 54 54 111 446 900 1001 1210 1210 2434 3000 9999 9999