CODEWITHSUNDEEP
c++sorting
user466534
user466534

Reputation:

implementation counting sort

here is code for counting sorting

#include <iostream>
using namespace std;

int main(){
    int a[]={2,3,1,2,3};
    int n=sizeof(int)/sizeof(int);
    int max=a[0];
    for (int i=1;i<n;i++) {
        if (a[i]>max) { 
            max=a[i];
        }
    }

    int *output=new int[n];
    for (int i=0;i<n;i++) {
        output[i]=0;
    }
    int *temp=new int[max+1];
    for (int i=0;i<max+1;i++) {
        temp[i]=0;
    }
    for (int i=0;i<n;i++){
        temp[a[i]]=temp[a[i]]+1;
    }
    for (int i=1;i<max+1;i++) {
        temp[i]=temp[i]+temp[i-1];
    }
    for (int  i=n-1;i>=0;i--) {
        output[temp[a[i]]-1]=a[i];
        temp[a[i]]=temp[a[i]]-1;
    }
    for (int i=0;i<n;i++) {
        cout<<output[i]<<"  ";
    }
    return 0;
}

but output is just 2,only one number. what is wrong i can't understand please guys help me

Upvotes: 0

Views: 8549

Answers (3)

Jerry Coffin
Jerry Coffin

Reputation: 490108

My advice would be that if you're going to do this in C++, you actually try to use what's available in C++ to do it. I'd look up std::max_element to find the largest element in the input, and use an std::vector instead of messing with dynamic allocation directly.

When you want the number of elements in an array in C++, you might consider a function template something like this:

template <class T, size_t N>
size_t num_elements(T const (&x)[N]) { 
    return N;
}

Instead of dumping everything into main, I'd also write the counting sort as a separate function (or, better, a function template, but I'll leave that alone for now).

// warning: Untested code:
void counting_sort(int *input, size_t num_elements) { 
    size_t max = *std::max_element(input, input+num_elements);

    // allocate space for the counts.
    // automatically initializes contents to 0
    std::vector<size_t> counts(max+1); 

    // do the counting sort itself.
    for (int i=0; i<num_elements; i++)
        ++counts[input[i]];  

    // write out the result.
    for (int i=0; i<counts.size(); i++)
        // also consider `std::fill_n` here.
        for (int j=0; j<counts[i]; j++)
            std::cout << i << "\t";
}

int main() { 
    int a[]={2,3,1,2,3};

    counting_sort(a, num_elements(a));
    return 0;
}

Upvotes: 1

abelenky
abelenky

Reputation: 64682

Look at this expression:

int n=sizeof(int)/sizeof(int);

What do you think the value of n is after this? (1)
Is that the appropriate value? (no, the value should be 5)
Does that explain the output you are seeing? (yes, that explains why only one number is shown)

Upvotes: 1

David Heffernan
David Heffernan

Reputation: 612884

int n=sizeof(int)/sizeof(int);

is wrong. That just assigns 1 to n.

You mean

int n=sizeof(a)/sizeof(int);

I've not looked beyond this. No doubt there are more problems, but this is the most significant.

This is the kind of thing you can work out very easily with a debugger.

Upvotes: 2

Related Questions