Быстрая и распределяющая сортировки
В представленной ниже программе функция 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);
}
На рис.31 показана схема включения очередного элемента списка в К-й карман.
Рис.31. Схема включения очередного элемента списка в карман.
Разновидностью распределяющей сортировки является битовая сортировка. В ней элементы
списка интерпретируются как двоичные числа, и D(j,n) обозначает j-ю справа двоичную
цифру числа n. При этой сортировке в процессе РАСПРЕДЕЛЕНИЕ требуются только два
вспомогательных кармана В0 и В1; их можно разместить в одном массиве, двигая списки В0 и
В1 навстречу друг другу и отмечая точку встречи. Для осуществления СБОРКИ нужно за
списком В0 написать инвертированный список В1.
Так как выделение j-го бита требует только операций сдвига, то битовая сортировка
хорошо подходит для внешней сортировки на магнитных лентах и дисках.
Разновидностью битовой сортировки является бинарная сортировка. Здесь из всех элементов
списка B= выделяются его минимальный и максимальный элементы и находится их среднее
арифметическое m=(MIN+MAX)/2. Список В разбивается на подсписки В1 и В2, причем в В1
попадают элементы, не большие m, а в список В2 - элементы, большие m. Потом для непустых
подсписков В1 и В2 сортировка продолжается рекурсивно.