countsort.c

/*
 *  Writen [email protected]屎壳郎
 *  Jan 2021
 *  Rev:0 
 *
 *  @Algorithm C (Comparision counting)
 *     C1.[Clear COUNTs] Set COUNT[1] through COUNT[N]to zero.
 *     C2.[Loop on i.] Perform step C3, for i=N,N-1.....2;
 *                     then terminate the algorithm. 
 *     C3.[Loop on j] Perform step C4, for j=i-1,i-2,...1.
 *     C4.[Compare Ki:Kj] If Ki<Kj, increase COUNT[J] by one;
 *                        otherwise increase COUNT[i] by 1.
 */

#include <sort.h>


void countsort(int *array, const unsigned int arraylen)
{
  int aux[arraylen];
  for(int i = 0; i < arraylen; i++){ aux[i] = 0;}/* Set all count set to zero */
  
  for(int i = 1; i < arraylen; i++){
    aux[i] = i;
    for(int j = 0; j < i; j++){
      if(array[i] < array[j]){
	/* Improved by 5.2.1-ex8 */
	  aux[i] -= 1;
	  aux[j] += 1;
      }
      /*
      else{
	count[i] += 1;
      }
      */
    }
  }

    
    /* sort depended by auxtable on array. */
    int k, j;
    int R, S;			/* According the discribe of alg. */
    while(r >= 0){
      if( r >= aux[r]){
	r -= 1;
	continue;
      }
      
      R = array[r];
      j = aux[r];
      while(j != r){
	S = array[j];
	k = aux[j];
	array[j] = R;
	R = S;
	j = k;
      }
      array[j] = R;
      r -=1;
    }
}
 


/* #include  <stdio.h>  */
/* #include  <ds.h> */
/* int main(void)  */
/* { */
/*   int x[] = {1,7,5,4,2,9,6,8,3}; */
/*   countsort(x, 9);  */
/*   _showarray(x, 9);  */
/* }  */