Sunday, August 28, 2016

COUNTING SORT WITH NEGATIVE VALUE

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int temp_p[100];
    int temp_n[100];
    int m,n,i,x;
    int j=0;
    int p=0;
    cout<<"Total number : ";
    cin>>n;
    cout<<"Maximum number : ";
    cin>>m;
    int pos[m+1];
    int neg[m+1];
    memset(pos, 0, sizeof pos);
    memset(neg, 0, sizeof neg);
    for(i=0;i<n;i++){
        cin>>x;
        if(x>=0){
            temp_p[j]=x;
            pos[x]++;
            j++;
        }
        else{
            temp_n[p]=x*-1;
            neg[x*-1]++;
            p++;
        }
    }
    for(i=1;i<=m;i++){
        pos[i]=pos[i]+pos[i-1];
        neg[i]=neg[i]+neg[i-1];
    }
    int arry_p[j];
    int arry_n[p];

    for(i=0;i<j;i++){
        int b=temp_p[i];
        arry_p[pos[b]-1]=b;
        pos[b]--;
    }
    for(i=0;i<p;i++){
        int b=temp_n[i];
        arry_n[neg[b]-1]=b;
        neg[b]--;
    }
    for(i=p-1;i>=0;i--){
        cout<<(arry_n[i]*-1)<<" ";
    }
    for(i=0;i<j;i++){
        cout<<arry_p[i]<<" ";
    }
    cout<<endl;


    return 0;
}

No comments:

Post a Comment