counting sort using c++

Question

#include<iostream>
#include <fstream>
#include <algorithm>
using namespace std;

void countsort(int a[], int b[], int n, int k, int& count) {
    int *c = new int[k + 1];

    for (int i = 0; i <= k; i++) {
        count = count + 1;
        c[i] = 0;
    }
    for (int j = 0; j < n; j++) {
        count = count + 1;
        c[a[j]]++;
    }
    
    
    for (int i = 1; i <= k; i++) {
        count = count + 1;
        c[i] = c[i] + c[i - 1];
    }
    int x;
    for (int j = n - 1; j >= 0; j--) {
        count = count + 1;
        x=c[a[j]]-1;
        b[x] = a[j];
        c[a[j]]--;
    }
    
    delete[] c;
}

int main() {
    ifstream fin;
    int n;
    int* a;
    int* b;
    string fname;
    int count = 0;

    cout << "enter file name" << endl;
    cin >> fname;
    cout << "enter arr size" << endl;
    cin >> n;
    fname += ".txt";
    fin.open(fname);
    a = b = new int[n];
    for (int i = 0; i < n; i++) {
        fin >> a[i];
    }
    fin.close();
    // unsorted array
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    int k = *max_element(a, a + n);
    cout<<endl<<k<<endl;

    countsort(a, b, n, k, count);

    // Output sorted array
    for (int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
    cout << endl;

    cout << "Number of operations: " << count << endl;

    delete[] a;
    delete[] b;

    return 0;
}

THE output in array b is wrong and i don't know what mistake i have done

the input

3
4
3
2
0
2
0
0
0
2

the output 2 2 2 2 2 2 2 0 0 2

ai websites can't find the problem, i also tried printing the array in between the code to see where the output goes wrong and i think there is mistake in this region

for (int i = 1; i <= k; i++) {
        count = count + 1;
        c[i] = c[i] + c[i - 1];
    }

    for (int j = n - 1; j >= 0; j--) {
        count = count + 1;
        x=c[a[j]]-1;
        b[x] = a[j];
        c[a[j]]--;
    }
 

the complete output i get is

enter file name input_csort_1 enter arr size 10 3 4 3 2 0 2 0 0 0 2 4 2 2 2 2 2 2 2 0 0 2 Number of operations: 29

Answer 1

Your program has several problems, but your biggest issue is that your code is overly complicated and not well structured.

First, try breaking down the algorithm into its essential steps: Initializing the count array, populating the counts from the input array, populating the output array from the counts. Keep breaking these steps down further until you have a very clear idea what needs to be done for each step. For example, populating the output array may require writing multiple outputs for each entry in the count array. Make sure you understand how to do that. Take notes on a sheet of paper if that helps you. At this first stage you do not need to write code. This is about getting a clear picture in your head what it is that you are trying to do.

Next, you want to solve each of those little problems in isolation. Write a little piece of code that just initializes the count array. The code should be small enough that you know what is going on at each line that you write, and what the value of each variable should be. This is clearly not the case in your function right now, as you, for example, keep increasing the count variable for no good reason and keep confusing the meaning of n and k.

Keep the code small enough that you don't get confused in this way, and choose your variable names in a way that it is easy for you to remember what they do. Once you have finished writing a piece of code, you should test it right away, in isolation. If it does not behave as expected, you will only have to fix a very small section of code, which is much easier than fixing a complex algorithm.

Solve each step in isolation and test it on its own first. This may seem like it's slowing you down at first, but it's not. It keeps things manageable and tidy.

Once you are certain that you have implemented all of the individual steps correctly, you put it together in the bigger algorithm. If something doesn't work, make sure you trace down the step that failed and again test that step in isolation for the inputs for which it fails.

Rinse and repeat until you have a working program. Happy coding!