Имеется массив из n чисел от 0 до (2 в степени k) - 1, каждое из которых мы будем рассматривать как k-бит

[alykaa]

помогите, пожалуйста, решить задачку. Имеется массив из n чисел от 0 до (2 в степени k) - 1, каждое из которых мы будем рассматривать как k-битовое слово. Используя проверки "i-ый бит равен 0" и "i-ый бит равен 1" вместо сравнений, отсортировать все числа за время порядка n*k.

[Stilet]

Ух ты... Чем дальше в лес тем методички извращеннее становятся...
Можешь пояснить на пальцах условие... Я не сильно понял

[alykaa]

я сама не сильно поняла, но как мне сказали надо почитать цифровую сортировку, и типа сравнивать по битам 1 и 0

[Stilet]

за время порядка n*k.

Вот это мне не понятно...
Допустим если взять банальную сортировку то:

for i:=1 to 10 do begin
 for j:=1 to 10 do begin
  if (a[i] and e)<(a[j] and e) then begin
   temp:=a[i];a[j]:=a[i];a[i]:=temp;
  end;
 end;
end;

А типа так...

[evg_m]

1.собрать слева (0*****) и справа (1*******) и точка раздела n1
за один проход цикла (N) (вполне реализуемо).
затем
2.1 (00****) (01****) до n1(там где у нас (0******)) и точка n21
2.2. (10****)(11****) от n1(там где у нас (1******)) b точка n22
еще один проход цикла (n1 +(N-n1) =N)
....
K.1
k....
k.2^k
последний проход цикла (N)
итого N*K.

принципальная схема реализации одного из перечисленных выше пунктов (без определения точек раздела n1,.... ).

i:=0;
j:=n-1;
m:=1 shl k;
while i<j do
begin
  if (a[i] and m) =0 then begin i:=i+1; continue; end;
  if (a[j] and m)>0 then begin j:=j+1; continue; end;
  r:=a[i]; a[i]:=a[j]; a[j]:=r; 
end;

[alykaa]

evg_m, не могли бы Вы более подробно написать, потому,что я сама не программист, и мне немного тяжеловато