febb

Поэтому будет исключительно программистский пост!

avva пишет:
Владимир Ярославский из Сана придумал новый вариант Квиксорта, работающий быстрее обычного. Основная идея проста до безобразия: вместо одного опорного элемента (pivot) выбираем два, распихиваем элементы в три подмассива: меньше первого опорного, между первым и вторым, и больше второго, и спускаемся рекурсивно три раза вместо обычных двух.

А я вот как-то выдумал алгоритм в несколько раз быстрее квиксорта для массивов строк.
Наверное он похож на алгоритм Седжвика, но мне кажется должен быть быстрее.
Идея такая:
Рекурсивно, начиная со старшего байта:
1) вычисляем гистограмму встречающихся байт и сортируем на 256 кусков в один проход
2) для каждого из 256 кусков повторяем 1) для следующего байта и т.д.

Конечно для ограничения вырождения алгоритм нужно усложнить и т. п.
Но вот на самом примитивном уровне как он выглядит на С++:


void ByteSort(char ** Array, size_t Num, size_t size, size_t offset=0)
{
    size_t S[256],  // starting index per group
			H[256];    // (histogram) number of elements in group
    // init historgram:
	memset(H, 0, sizeof(H));
    // 1st path: make historgram of byte values:
	register unsigned char ** data = (unsigned char **)Array;
	register size_t i;
    for(i=0; i < Num; i++)
        ++H[ data[i][offset] ];
    // calculate staring index positions:
    size_t s = 0;
    for(i=0; i < 256; i++)
        { S[i] = s;  s += H[i]; }
    // sorting by regrouping data:
	unsigned char ** ds = new unsigned char * [ Num ]; // allocate temp array for sorted elements
	for(i=0; i < Num; i++)
		{
		unsigned char * d = data[i];
		ds[ S[ d[offset] ]++ ] = d;			// increment current position and copy element
		}
	memcpy(data, ds, sizeof(*data)*Num);	// copy sorted array back
	delete [] ds; // free mem
    // sort recurecively all the groups:
    if(--size)
        {
        ++offset;
	    s = 0;
        for(i=0; i < 256; i++)
			{
			size_t h = H[i];
            if(h > 1)
                ByteSort(Array + s, h, size, offset);
			s += h; //calculate starting index
			}
        }
}

Мне интересно, кто-нибудь теоретически может оценить, насколько он быстрее?
По тестам со случайными массивами работает раз в 10 быстрее квиксорта.
Плохие случаи я не исследовал.

Всех программистов с Праздником!