Программирование на языке С - Быстрая и распределяющая сортировки
ОГЛАВЛЕНИЕ
2.2.6. Быстрая и распределяющая сортировки
Быстрая сортировка состоит в том, что список В= реорганизуется в список B',,B", где В' - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B',,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B' и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками <и>.
Пример:
9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26
7, 3, 4, 6, 8, 5/ <9>/ 18, 52, 13, 42, 30, 35, 26
3, 4, 6, 5/<7>/ 8/ 9/ 13/ <18>/ 52, 42, 30, 35, 26
<3>/ 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/ <52>
3/ <4>/ 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ <42>/ 52
3/ 4/ 5/ <6>/ 7/ 8/ 9/ 13/ 18/ 26/ <30>/ 35/ 42/ 52
Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B' и В" приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов.
Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.
/* быстрая сортировка */
double * quick(double *s,int low,int hi)
{ double cnt,aux;
int i,j;
if (hi>low)
{ i=low;
j=hi;
cnt=s[i];
while(i < j)
{ if (s[i+1]<=cnt) { s[i]="s[i+1];" s[i+1]="cnt;" i++; } else { if (s[j]<="cnt)"
{ aux="s[j];" s[j]="s[i+1];" s[i+1]="aux;" } j--; } } quick(s,low,i-1); quick(s,i+1,hi); } return(s); } Здесь используются два индекса i и j, проходящие части массива навстречу друг другу. При этом i всегда фиксирует разделяющий элемент cnt=s[low], слева от которого находятся числа, не большие cnt, а справа от i - числа, большие cnt. Возможны три случая: при s[i+1]<=cnt; при s[i+1]>cnt и s[j]<=cnt; при s[i+1]>cnt и s[j]>cnt. По окончании работы i=j, и cnt=s[i] устанавливается на своем месте.
Быстрая сортировка требует дополнительной памяти порядка log2(N) для выполнения рекурсивной функции quick (неявный стек).
Оценка среднего количества действий, необходимых для выполнения быстрой сортировки списка из N различных чисел, получена как оценка отношения числа различных возможных последовательностей из N различных чисел, равного N!, и общего количества действий C(N), необходимых для выполнения быстрой сортировки всех различных последовательностей. Доказано, что C(N)/N! <2*N*ln(N).
Распределяющая сортировка. Предположим, что элементы линейного списка В есть Т-разрядные положительные десятичные числа 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);
}
Разновидностью распределяющей сортировки является битовая сортировка. В ней элементы списка интерпретируются как двоичные числа, и 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 сортировка продолжается рекурсивно.