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

[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;
  }}