Feeds:
Posts
Comments

Posts Tagged ‘sorting in linear time’

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.

Advertisements

Read Full Post »