|
===========================================================================
> 11. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?
===========================================================================
A: Kantor Ilia
Пусть имеем максимум по k байт в каждом ключе ( хотя за элемент
сортировки вполне можно принять и что-либо другое, например слово -
двойной байт, или буквы, если сортируются строки). k должно быть
известно заранее, до сортировки.
Разрядность данных ( количество возможных значений элементов ) - m,
также должна быть известна заранее и постоянна.
Если мы сортируем слова, то элемент сортировки - буква. m = 33.
Если в самом длинном слове 10 букв, k = 10.
Обычно мы будем сортировать данные по ключам из k байт, m=256.
----------------------------------------------------------------------
Пусть у нас есть массив source из n элементов по одному байту в каждом.
Для примера можете выписать на листочек массив
source[1..7] = { 7,9,8,5,4,7,7 }, и проделать с ним все операции,
имея в виду m=9. n здесь, очевидно, равно 7.
I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и
заполняться она будет так:
for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;
Для нашего примера будем иметь distr = { 0,0,0,0,1,1,0,3,1,1 },
то есть i-ый элемент distr[] - количество ключей со значением i.
Заполним таблицу индексов:
int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];
В index[i] мы поместили информацию о будущем количестве символов в
отсортированном массиве до символа с ключом i.
Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.
А теперь восстановим уже отсортированный массив sorted размера n:
for ( i = 0; i < n ; i++ )
{
sorted[ index[ source[i] ] ]=source[i];
// попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
index[ source[i] ] = index[ source[i] ] +1;
}
Проще всего понять, почему все получается, можно проделав все операции
на бумаге.
Итак, мы научились за O(n) сортировать байты. А от байтов до строк
и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.
Будем действовать в десятичной системе и сортировать обычные числа
( m = 10 ).
сначала они в сортируем по по разряду
беспорядке: младшему разряду: левее: и еще раз,:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554
/|\ /|\ /|\
| | |
Вот мы и отсортировали массив за O(kn) шагов. Если количество
возможных различных ключей ненамного превышает общее их число, то
поразрядная сортировка оказывается гораздо быстрее даже 'быстрой
сортировки' !
Распределяющая сортировка, требует O(n) дополнительной памяти.
Пример(учебный) реализации radixsort на Си++ для long int'ов.
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
void radix (int byte, long N, long *source, long *dest)
{
// *source - входной массив,
// *dest - отсортированный.
long count[256]; // вообще говоря, можно обойтись
long index[256]; // одним массивом count[]
memset (count, 0, sizeof (count));
for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
index[0]=0;
for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
for(i=0;i<N;i++) dest[index[((source[i])>>(byte*8))&0xff]++]=source[i];
}
void radixsort (long *source, long *temp, long N)
{
// Сортируем по всем 4 разрядам
radix (0, N, source, temp);
radix (1, N, temp, source);
radix (2, N, source, temp);
radix (3, N, temp, source);
}
void make_random (long *data, long N)
{
for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
}
long data[10000];
long temp[10000];
void main (void)
{
make_random(data, 10000);
radixsort (data, temp, 10000);
for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
}
Примечания.
1. К сожалению, или к счастью, единица информации в современной
технике способна принимать лишь 2 значения: 1 и 0.
А значит, любые компьютерные данные тоже могут принимать
ограниченное количество значений, так как состоят из некоторого
числа битов ;-)).
Таким образом, распределяющая сортировка потенциально применима
где угодно. Другое дело, что если разрядность данных большая
по сравнению с общим количеством элементов, то скорость работы
оставит желать много лучшего.
2. Алгоритм, описанный выше, очевидно, требует O(n) памяти.
Существует похожий алгоритм, использующий лишь O(logn).
Модифицированная Radix Sort:
Будем сортировать по каждой позиции символа 'на месте', начиная справа:
сначала сортируем по первой позиции, затем к каждой части массива,
относящейся к одному и тому же значению, рекурсивно
применяем ту же процедуру и т.д.
Этот вариант называется 'Radix exchange sort' и
представляет собой скорее разновидность QuickSort.
Hа мой взгляд, она объединяет больше плохих черт обоих методов,
нежели хороших, но вполне может пригодиться в какой-то ситуации.
> Существует вариант распределяющей сортировки для списков,
> каждый элемент которых принимает конечное множество значений.
> Он даже проще в реализации, понимании и использовании.
Предположим, что элементы линейного списка В есть Т-разрядные
положительные десятичные числа D(j,n) - j-я справа цифра в десятичном
числе n>=0, т.е. D(j,n)=floor(n/m)%10, где m=10^(j-1).
(floor - округление в меньшую сторону)
Пусть В0,В1,...,В9 - вспомогательные списки (карманы), вначале пустые.
Для реализации распределяющей сортировки выполняется процедура,
состоящая из двух процессов, называемых распределение и сборка
для j=1,2,...,T.
PАСПРЕДЕЛЕHИЕ
заключается в том, что элемент Кi (i=1,N) из В добавляется как
последний в список Bm, где m=D(j,Ki), и таким образом получаем
десять списков, в каждом из которых j-тые разряды чисел одинаковы и
равны m.
СБОРКА
объединяет списки В0,В1,...,В9 в этом же порядке,
образуя один список В.
> Число карманов - количество возможных значений элемента списка.
Исходный список можно сделать односвязный, а сортировку организовать так,
чтобы для карманов В0,В1,...,В9 не использовать дополнительной памяти, т.е
элементы списка не перемещать, а с помощью перестановки указателей
присоединять их к тому или иному карману.
В представленной ниже программе функция pocket реализует распределяющую
сортировку связанного линейного списка (указатель q), в котором содержатся
Т-разрядные десятичные положительные числа, без использования
дополнительной памяти;
в функции a[i], b[i] указывают соответственно на первый и на последний
элементы кармана Bi.
/* распределяющая сортировка списка */
#include <stdlib.h>
#include <stdio.h>
typedef struct SP1_ {
long val;
struct SP1_ *next;
} SP1;
/* функция сортировки возвращает указатель на начало
отсортированного списка */
SP1 *pocket(SP1 *q,int t) {
/* 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->next=q;
r=b[k]=q;
q=q->next;
r->next=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->next=a[k];
r=b[k];
}
m=m*10;
}
return (gg);
}
/* Тестовая программа */
void main() {
int i;
SP1 *q, *r;
/* Это будем сортировать */
long a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
q=(SP1 *)malloc(sizeof(SP1));
q->val=a[0];
r=q;
for(i=1;i<14;i++) { /* формирование списка */
r->next=(SP1 *)malloc(sizeof(SP1));
r->next->val=a[i];
r=r->next;
}
r->next = NULL;
/* Список сформирован, q указывает на начало */
r=pocket(q,2); /* Запускаем сортировку */
printf("\nresult:\n"); /* печать результатов */
while (r!=NULL) {
printf(" %d",r->val);
r=r->next;
}
}
|
