Нужна помощь!

[maximys]

Имеется псевдокод Рекурсивного алгоритма поразрядной MSD-сортировки

Код:

MSD_Sort (A, l, r, d, C)
1.	 А – массив
2.	 С – вспомогательный массив для карманов
3.	 l, r – левая и правая границы части массива A 
4.	 R – основание системы счисления для поразрядной сортировки
5.	 k – максимальное количество цифр в значениях
6.	 d – номер текущей цифры
7.	 M – пороговый размер кармана для окончания рекурсии
8.	k← bitsword / bitsdigit  bitsword – число битов в ячейке мас-сива А
9.				        bitsdigit – число битов в цифре
10.	if d > k
11.	     then return
12.	if r – l   M
13.	     then  Insertion_Sort(A + l, r – l)
14.	               return
15.	  вычисление размеров карманов
16.	for j ← 1 to R + 1
17.	     do count[j] ← 0
18.	for i ← l to r
19.	     do j ← digit(A[i], d, R)	 digit(…) – извлечение d-й цифры
20.	          count[j + 1] ← count[j + 1] + 1
21.	for j ← 2 to R
22.	     do count[j] ← count[j] + count[j – 1]
23.	 распределение значений по карманам
24.	for j ← l to r
25.	     do j ← digit(A[i], d, R)
26.	          C[l + count[j]] ← A[i]
27.	          count[j] ← count[j] + 1
28.	  перенос значений из карманов в массив A
29.	for i ← l to r
30.	     do A[i] ← C[i]
31.	MSD_Sort (A, l, l + count[1], d + 1, C)
32.	for i ← 2 to R
33.	     do MSD_Sort (A, l + count[i], l + count[i + 1] – 1, d + 1, C)

Нужно перевести этот псевдокод в код на С++.Помогите кто может.

[Алексей++]

какой размер массива А и его тип ?

какие типы переменных

Код:

l, r, d, C

?

как понять выражение

Код:

l, r – левая и правая границы части массива A 

?

непонятно начальное значение переменной i в выражениях твоего кода типа

Код:

for i < l to r

[maximys]

какой размер массива А и его тип ?

Тип массива произвольный(класс), а размер можно обозначить переменной maxN(размерность увеличивается, будет прописано в другом методе)Н-р:

Код:

Vector С[maxN];

какие типы переменных

int

как понять выражение:  l, r – левая и правая границы части массива A?

так и понимать..?

непонятно начальное значение переменной i в выражениях твоего кода типа:for i < l to r

for i ← l to r // символ "←" это символ присваивания, а "l"- это буква

И ещё в 12ой строчке

Код:

12.	if r – l  < M //минимальный размер корзины

[Алексей++]

уфф, в общем я запутался в твоих переменных и необъявленных массивах ))) , но что то вроде этого должно получиться

Код:

typedef DWORD vector;

void MSD_Sort(vector* A, int l, int r, int d, vector* C)
{

//	А[l...r] - массив
//	С[l...r] - вспомогательный массив для карманов
//	l, r - левая и правая границы части массива A 

	int R=2;// - основание системы счисления для поразрядной сортировки

	//максимальное количество цифр в значениях
	int k=10;

	//номер текущей цифры
	int D=0;

	//пороговый размер кармана для окончания рекурсии
	int M=100;//?

	//
	int bitsword=8;// - число битов в ячейке мас-сива А
	int bitsdigit=8;// - число битов в цифре

	k= bitsword / bitsdigit;//  

	if(d > k)return;

	if (r - l >   M) // знак сравнения какой ?
	{
		Insertion_Sort(A + l, r - l);
		return;
	}

	//вычисление размеров карманов
	for(j=1; j<=R+1; j++)
	{
		count[j] = 0;
	}

	for(i=l;i<=r;i++)
	{
		j = digit(A[i], d, R);//digit(...) - извлечение d-й цифры
		count[j + 1] = count[j + 1] + 1;
	}

	for(j=2;j<=R;j++)
	{
		count[j] < count[j] + count[j - 1];
	}

	//распределение значений по карманам
	for(j=l;j<=r;j++)
	{
		j = digit(A[i], d, R);
		C[l + count[j]] < A[i];
		count[j] < count[j] + 1;
	}

	//перенос значений из карманов в массив A
	for(i=l;i<=r;i++)
	{
		A[i] = C[i];
	}

	MSD_Sort (A, l, l + count[1], d + 1, C);
	for(i=2;i<=R;i++)
	{
		MSD_Sort (A, l + count[i], l + count[i + 1] - 1, d + 1, C);
	}
}

//пример вызова
void F()
{
	#define maxN 10

	vector A[maxN];
	vector C[maxN];

	MSD_Sort(A, 0, maxN-1, 2, C);
}

[maximys]

Довел до ума сортировку, вот что получилось

Код:

template <class T> void Vector <T>::Sort ()
{

        MSD_Sort (mass,0, size0,0,C);
}

template <class T> void Vector <T>::MSD_Sort (T* mass,int l, int r, int d, T *C)
{

int R=16;// - основание системы счисления для поразрядной сортировки
int count[100];
int bitsword,bitsdigit,k;
int i,j;
   bitsword = sizeof(int) * 8; // - число битов в ячейке мас-сива А
   bitsdigit = ceil(log(R)/log(2));// - число битов в цифре
	//максимальное количество цифр в значениях
	 k=ceil(1.0* bitsword/bitsdigit);

	//пороговый размер кармана для окончания рекурсии
	int M=100;//?

	if(d > k)return;

	if (r - l <=   M)
	{
		Insertion_Sort(mass + l, r - l);
		return;
	}

	//вычисление размеров карманов
	for(j=1; j<=R+1; j++)
	{
		count[j] = 0;
	}

	for(i=l;i<=r;i++)
	{
		j = (mass[i]>>bitsdigit*(bitsword-d-1)&(R-1));

		count[j + 1] = count[j + 1] + 1;
	}

	for(j=2;j<=R;j++)
	{
		count[j] < count[j] + count[j - 1];
	}

	//распределение значений по карманам
	for(j=l;j<=r;j++)
	{
		j = (mass[i]>>bitsdigit*(bitsword-d-1)&(R-1));
		C[l + count[j]] < mass[i];
		count[j] < count[j] + 1;
	}

	//перенос значений из карманов в массив A
	for(i=l;i<=r;i++)
	{
		mass[i] = C[i];
	}

	MSD_Sort (mass, l, l + count[1], d + 1, C);
	for(i=1;i<=R;i++)
	{
		MSD_Sort (mass, l + count[i], l + count[i + 1] - 1, d + 1, C);
	}
}

void  Insertion_Sort(T* mass,int n){
  int k,i,j;
  for(  i=1; i<n; i++){
  int v=mass[i];
  for( k=0; k<i; k++)
  if(mass[k]>v) break;
  for( j=i-1;j>=k;j--)
  mass[j+1]=mass[j];
  mass[k]=v;
  }}