Поразрядная сортировка в C++

а из википедии не пашет ?

google::codesearch("radix_sort"), первая ссылка.

предлагаю направить запрос в минобразования на введение в школах уроков пользования гуглов с занесением итоговой отметки в аттестат.

; sexter

>предлагаю направить запрос в минобразования на введение в школах уроков пользования гуглов с занесением итоговой отметки в аттестат.

Какой такой гугл, когда яндекс.бар закуплен?

> а из википедии не пашет ?

ну вот смотри

int bit (int a, int i)
{
return (a >> i) & 1;
}
void radix_sort (int a[], int l, int r, int b)
{
int i, j;
if (r <= l || b < 0) return;
i = l;
j = r;
while (i < j)
{
while (i < j && bit (a[i], b) == 0) ++ i;
while (i < j && bit (a[j], b) == 1) -- j;
swap (a[i], a[j]);
}
if (bit (a[r], b) == 0) ++ j;
radix_sort (a, l, j - 1, b - 1);
radix_sort (a, j, r, b - 1);
}

в void radix_sort (int a[], int l, int r, int b) я не могу понять как задать переменные,
int a[] - входной и выходной массив (правильно понял?)
int l - length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове)
int r - range - количество возможных значений одного разряда (при сортировке слов - количество букв в алфавите)
int b - что четвертым аргументом идет?

дайте эту функцию на примере работающую

> int a[] - входной и выходной массив (правильно понял?)

да

> int l - length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове)

нет. в данном случае l это с какого индекса нужно начинать сортировать, то есть в первом вызове должен быть ноль.

> int r - range - количество возможных значений одного разряда (при сортировке слов - количество букв в алфавите)

нет. Твой пример сортирует целые числа побитово. То есть range равен 2 по определению.

r это верхняя граница, до какого элемента нужно сортировать, то есть это должен быть индекс последнего элемента массива.

> int b - что четвертым аргументом идет?

это номер бита по которому нужно сортировать. То есть при первом вызове это должен быть номер самого старшего бита. (то есть b это как раз length в твоем первоначальном понимании)

Всё, я разобрался с этим, жестка тупил, но разобрался.. =) кому интересно - я положил в - Википеди - Поразрядная сортировка - С++ (еще один пример), в нем принцип действия её оч. хорошо проилюстрирован.

в английской статье про radix_sort сумели обойтись без кучи непонятного кода

#include <iostream>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include <vector>

using namespace std;

template <typename FDIter>
void radixSort(FDIter first, FDIter last){
const int RADIX_SORT_NUM_PLACES = 5;
int powerOfTen = 1;
for (int place = 0; place < RADIX_SORT_NUM_PLACES; ++place){
vector<vector<int> > buckets(10);
for (FDIter it=first;it!=last;++it){
buckets[((*it)/powerOfTen)%10].push_back(*it);
}
FDIter copyBack = first;
for (int i = 0; i < 10; ++i){
copyBack=copy(buckets[i].begin(),buckets[i].end(),copyBack);
}
powerOfTen*=10;
}
}

int main(){
int n=90,i;
float a=0.5,b=17.1;

float arr[n];

for(i=0;i<n;i++){
arr[i]=a+(b-a)*(double)rand()/(double)RAND_MAX;
}
cout<<"Polu4eniiy massiv: \n";
for(i=0;i<n;i++){
cout<<arr[i]<<" ";
}
radixSort(arr, arr+n);
cout<<"\nOtsortirovan porazryadnoi sortirovkoi: \n";
for(i=0;i<n;i++){
cout<<arr[i]<<" ";
}

getch();
return 0;
}

при сортировке вещественного массива
в функции radixSort руается на несовместимость float и бинарного % в
buckets[((*it)/powerOfTen)%10].push_back(*it);
как обойти?

> в английской статье про radix_sort сумели обойтись без кучи непонятного кода

да, сумели обойтись только объяснением что это такое и что это слово вообще значит.. =)

> как обойти?

стенку не обойдешь..

Кстати, кому-нибудь удавалось обогнать std::sort на int'ах? скажем 40000000 int'ов и 1 гиг оперативы.

Обходить то должна, т.к. с линейной сложностью, а std::sort за n*ln(n),
ясно, что они где-то пересекуься, но я сколько не мучался, не 
получалось, вот код:

template <class T>
void my_radix_sort(vector<T>& v)
{
	std::vector<T> buckets[256];
	int sizes[256];

	for (int i=0;i<256;i++)
		sizes[i]=0;

	size_t v_size = v.size();

	int mask[] = {255,65280,16711680,-16777216};

	for (int r = 0; r < 4; r++)
	{
		//const int mask = (0xff) << (8 * r);
		int cmask = mask[r];
		
		unsigned char b;
		for (size_t i = 0; i < v_size; ++i)
		{
			b = (v[i] & cmask) >> (8 * r);
			sizes[b]++;
		}
	}

	for (int i=0;i<256;i++)
		buckets[i].reserve(sizes[i]);

	for (int r = 0; r < 4; r++)
	{
		int cmask = mask[r];
		
		T val;
		unsigned char b;
		for (size_t i = 0; i < v_size; ++i)
		{
			b = (v[i] & cmask) >> (8 * r);
			buckets[b].push_back(v[i]);
		}
		
		int k=0;
		for (int j=0;j<256;j++)
		{
			//if (buckets[j].empty()) continue;
			size_t b_size = buckets[j].size();
			for (size_t l=0;l<b_size;l++)
				v[k++] = buckets[j][l];
			buckets[j].clear();
		}
	}
}

разница где-то в 1% (std::sort быстрее)