Программирование на языке C


Быстрая и распределяющая сортировки


Быстрая сортировка состоит в том, что список В=< K1,K2,...,Kn>

реорганизуется в список B',< K1 >,B", где В' - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B',< K1 >,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B' и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками < и >.

Пример:

9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26 7, 3, 4, 6, 8, 5/ / 18, 52, 13, 42, 30, 35, 26 3, 4, 6, 5// 8/ 9/ 13/ / 52, 42, 30, 35, 26 / 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/

3/ / 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ / 52 3/ 4/ 5/ / 7/ 8/ 9/ 13/ 18/ 26/ / 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 &lt j) { if (s[i+1]

Здесь используются два индекса i и j, проходящие части массива навстречу друг другу (см. рис.30). При этом i всегда фиксирует разделяющий элемент cnt=s[low], слева от которого находятся числа, не большие cnt, а справа от i - числа, большие cnt. Возможны три случая: при s[i+1]cnt и s[j]cnt и s[j]>cnt. По окончании работы i=j, и cnt=s[i] устанавливается на своем месте.

Рис.30. Схема быстрой сортировки.

Быстрая сортировка требует дополнительной памяти порядка 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= .




Начало  Назад  Вперед



Книжный магазин