Распределяющая сортировка. Предположим, что элементы линейного списка В есть Т-разрядные положительные десятичные числа D(j,n) — j-я справа цифра в десятичном числе n>=0, т.е. D(j,n)=floor(n/m)%10, где m=10^(j-1). Пусть В0,В1,...,В9 — вспомогательные списки (карманы), вначале пустые.
Для реализации распределяющей сортировки выполняется процедура, состоящая из двух процессов, называемых распределение и сборка для j=1,2,...,T. PАСПРЕДЕЛЕНИЕ заключается в том, что элемент Кi (i=1,N) из В добавляется как последний в список Bm, где m=D(j,Ki), и таким образом получаем десять списков, в каждом из которых j-тые разряды чисел одинаковы и равны m. СБОРКА объединяет списки В0,В1,...,В9 в этом же порядке, образуя один список В.
Рассмотрим реализацию распределяющей сортировки при Т=2 для списка: B=<09,07,18,03,52,04,06,08,05,13,42,30,35,26> .
      РАСПРЕДЕЛЕНИЕ-1:
B0=<30>,  B1=< >,  B2=<52,42>, B3=<03,13>, B4=<04>,
B5=<05,35>,  B6=<06,26>,B7=<07>, B8=<18,08>, B9=<09>.
      СБОРКА-1:
B=<30,52,42,03,13,04,05,35,06,26,07,18,08,09>
      РАСПРЕДЕЛЕНИЕ-2:
B0=<03,04,05,06,07,08,09>, B1=<13,18>, B2=<26>,
B3=<30,35>, B4=<42>, B5=<52>, B6=< >,B7=< >,B8=< >, B9=< >.
      СБОРКА-2:
B=<03,04,05,06,07,08,09,13,18,26,30,35,42,52>.
Количество действий, необходимых для сортировки N T-цифровых чисел, определяется как Q(N*T). Недостатком этого метода является необходимость использования дополнительной памяти под карманы. Однако можно исходный список представить как связанный и сортировку организовать так, чтобы для карманов В0,В1,...,В9 не использовать дополнительной памяти, элементы списка не перемещать, а с помощью перестановки указателей присоединять их к тому или иному карману.
В представленной ниже программе функция pocket реализует распределяющую сортировку связанного линейного списка (указатель q), в котором содержатся Т-разрядные десятичные положительные числа, без использования дополнительной памяти; в функции a[i], b[i] указывают соответственно на первый и на последний элементы кармана Bi.
/*   вызов  распределяющeй  сортировки  списка    */
#include
#include
typedef struct str
{ long val;
   struct str *n; } SP1;
main()
{ int i;
  SP1 *q=malloc(sizeof(SP1)),*r;
  SP1 *pocket(SP1 * ,int );
  long a[14]={ 0,7,18,3,52,4,6,8,5,13,42,30,35,26 };
  q->n=NULL;
  q->val=a[0];
  r=q;
  printf(" %d",a[0]);
  for(i=1;i<14;i++)    /*  формирование списка  */
    { r->n=malloc(sizeof(SP1));
      r->val=a[i];
     (r->n)->n=NULL;
      r=r->n;
      printf(" %d",a[i]);
    }
  r=pocket(q,2);
  printf("\n");          /*  печать результатов   */
  while (r!=NULL)
    { printf(" %d",r->val);
      r=r->n;
     }
}
/*   распределяющая  сортировка  списка   */
SP1 *pocket(SP1 *q,int t)
{ int i,j,k,m=1;
  SP1 *r, *gg, *a[10], *b[10];
  gg=q;
  for(j=1;j<=t;j++)
   {  for(i=0;i<=9;i++) a[i]=(b[i]=NULL);
      while(q!=NULL)
        {  k=((int)(q->val/m))%(int)10;
           r=b[k];
           if (a[k]==NULL) a[k]=q;
           else r->n=q;
           r=b[k]=q;
           q=q->n;
           r->n=NULL;
         }
      for(i=0;i<=9;i++)
      if (a[i]!=NULL) break;
      q=a[i];
      r=b[i];
      for(k=i+1;k<=9;k++)
      if(a[k]!=NULL)
        {  r->n=a[k];
           r=b[k];
         }
      m=m*10;
   }
  return (gg);
}