1

Here is an implementation of counting sort in c++11. It does not give any output. What possibly went wrong? Should not the std::copy copies back the sorted array to the original array?

void counting_sort::sort_array(int array[], int n)
{
std::vector <int> a;
a.insert(a.end(), &array[0], &array[n]);
std::vector <int> b;

auto k = *std::max_element(a.begin(), a.end());
auto m = *std::min_element(a.begin(), a.end());

auto x = k - m + 1;
std::vector<int>v(x);

    for(int i = 0; i < a.size(); i++)
        v[a[i]-m]++;

    for(int i = 1; i < v.size(); i++)
        v[i]=v[i]+v[i-1];

    for(int i = a.size()-1; i >= 0; i--)
        { 
        b[v[a[i]-m]-1] = a[i]; 
        v[a[i]-m]--; 
    }

std::copy(b.begin(), b.end(), array);

}

ARSN
  • 167
  • 1
  • 10
  • Your program exhibits undefined behavior. `b` is an empty vector, `b[i]` is invalid for any value of `i` – Igor Tandetnik Aug 09 '16 at 04:46
  • How do you suggest to fix it? I have another version using only arrays with segmentation fault here: http://stackoverflow.com/questions/38842681/segmentation-fault-chkstk-ms-c. Thanks. – ARSN Aug 09 '16 at 05:29
  • You fix it by resizing the vector to a necessary size. You know how to do it - you've done it with `v`. – Igor Tandetnik Aug 09 '16 at 05:45
  • I tried that. It still does not give any output. – ARSN Aug 09 '16 at 06:34
  • 1
    Following Igor's advice results in no output, but not a crash. You are now in a good position to step through the algorithm with a debugger and see where it deviates from the expected. – user4581301 Aug 09 '16 at 06:47
  • What do you mean by "output"? What output do you expect? Your code doesn't contain any library calls that may result in output being produced. – Igor Tandetnik Aug 09 '16 at 12:44
  • Yes, it is void. But it should modify the array so that it is sorted. The output is produced by the main function which is not here. I found out that the problem is with x value that can be very big. Consider if k = 2 billion and m = -2 billion, then x = 4 billion. What should I use to make sure it works with this range? – ARSN Aug 09 '16 at 13:27
  • Counting sort is not suitable in this case. https://en.wikipedia.org/wiki/Counting_sort : *"counting sort is an algorithm for sorting a collection of objects according to keys that are **small integers**"* (emphasis mine) – Igor Tandetnik Aug 09 '16 at 14:07

0 Answers0