Программирование на языке С
Страница 79. Быстрая и распределяющая сортировки

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 сортировка продолжается рекурсивно.