When I am reviewing GRE CS SUB material I meet counting sort. Counting sort is “a sort of sort” other than the common comparison sorts. It runs in linear time and uses the combination of indexed-based arrangement strategy and conception of “backet sorting” to determine the sorted order, thus not like comparison-based idea. Counting sort is stable.

However , the original version of counting sort has some unavoidable defects, due to its rigorously “number-index mapping” policy, that is, a number N must correspond with its position element c[N], which seems of convinience in some cases whist confronts limitation. For example, when the target array has negative integers , or even decimals , such sorting has no idea! Because the array index is neither negative nor nonintegral value. As though decimal is indeed out of handling capacity of this sorting , negative integers can be perfectly tackled , if we distend the original version a little. After a bust of thought I reap an enhenced code segment.

Code is rough and complied in VS2005 environment. I am neither a lust nor an expert about program, so have to use such heavy tool to build the light code. Must say, My feeling is Damn.

int *counting_sort( int *a , int number )

{

int max ,min, cLen , i , j , *b , *c;

if( !a )

return NULL;

/*

now the conception is expanded. we use a narrower range to build such a “statistical” array c

not only use max to limit its upper bound, but also min to limit its lower bound.

for example , if we have : 6 4 3 5

then we do not need : 0 1 2 3 4 5 6

we just construct such a “c” : 0 1 2 3 ( which can effectively cram “3” to “6”, totally 4 number )

thereby , such function can be expanded to sort arrays with negetive number.

for example , if we have : 1 3 -2

we can build c as : 0 1 2 3 4 5 , which can hold -2 -1 0 1 2 3 justly ( from -2 to 3 )

so the key of enhencement is realign the position for each a[i]’s position in c!

*/

max = Max( a , number);

min = Min( a, number );

cLen = max – min + 1;

b = (int*)calloc( number , sizeof(int) );

c = (int*)calloc( cLen , sizeof(int) );

if( !c || !b )

return NULL;

/*

offsets each a[i]’s position

note that here a[i]’s information will not be stored simply in c[a[i]],

actually , you should take care of the “min” value as the offset!

*/

for( i=0;i<number;i++ )

c[a[i]-min] += 1;

// set j as the initial position where the element is not 0

for( j=0;!c[j];j++);

for( i=j+1; i<cLen;i++ )

if( c[i] )

{

c[i]+=c[j];

j=i;

}

/*

supposing a[i]=k, actually k’s information is not in c[k],but in c[k-min],

so c[k-min]’s value should be used to adopt k( a[i] ) ‘s real position in b

*/

for( i=number-1 ; i>=0;i– )

{

b[c[a[i]-min]-1] = a[i];

c[a[i]-min]–;

}

free(c);

return b;

}

//find the max value in array a

int Max( int *a , int number )

{

int ret = *a, i;

for( i=0; i<number; i++ ,a++ )

if ( *a > ret )

ret = *a;

return ret;

}

//find the min value in array a

int Min( int *a , int number )

{

int ret = *a, i;

for( i=0; i<number; i++ ,a++ )

if ( *a < ret )

ret = *a;

return ret;

}

Then I discuss how to test the code. You pass the address of target array and the length of it as two parameters to function “counting_sort”. Note that such sorting must use an assitant array to restore all the reranged elements. So Result array will be a new one and its pointer is returned.

## Leave a Reply