Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Низкоуровневое программирование > Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.01.2011, 00:35   #1
Cobalt
 
Регистрация: 06.12.2006
Сообщений: 4
Смущение реализация Поразрядной сортировки RadixSort

Доброго времени суток ребят!

Я в асме полный чайник и ноль,но вот задали блин на нем алгоритм поразрядной сортировки накатать.Пытался нагуглить,нагуглил просто код этого алгоритма и инфу о нем:
Код:
Распределяющая сортировка - RadixSort - цифровая - поразрядная
Пусть имеем максимум по k байт в каждом ключе (хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки.
Разрядность данных ( количество возможных значений элементов ) - m, также должна быть известна заранее и постоянна. Если мы сортируем слова, то элемент сортировки - буква, m = 33. Если в самом длинном слове 10 букв, k = 10.
Обычно мы будем сортировать данные по ключам из k байт, m=256.

Пусть у нас есть массив source из n элементов по одному байту в каждом.

Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 }, и проделать с ним все операции, имея в виду m=9.

   1. I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и заполняться она будет так:

      for i := 0 to Pred(255) Do distr[i]:=0;
      for i := 0 to Pred(n) Do distr[source[i]] := distr[[i]] + 1;

      Для нашего примера будем иметь distr = ( 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 ), то есть i-ый элемент distr[] - количество ключей со значением i.

   2. Заполним таблицу индексов:

      index: array[0 .. 255] of integer;
      index[0]:=0;
      for i := 1 to Pred(255) Do index[i]=index[i-1]+distr[i-1];

      В index[i] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i.
      Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.


А теперь заполняем новосозданный массив sorted размера n:

for i := 0 to Pred(n) Do Begin
  sorted[ index[ source[i] ] ]:=source[i];
  { попутно изменяем index уже вставленных символов, чтобы одинаковые ключи шли один за другим: }
  index[ source[i] ] := index[ source[i] ] + 1;
End;


Итак, мы научились за O(n) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).

сначала они в  сортируем по младшему  на один
беспорядке:    разряду:               выше:    и еще раз:
 523           523                    523      088
 153           153                    235      153
 088           554                    153      235
 554           235                    554      523
 235           088                    088      554

Hу вот мы и отсортировали за O ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то 'поразрядная сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'!

Реализация алгоритма "распределяющей" сортировки:

Const
  n = 8;
  
Type
  arrType = Array[0 .. Pred(n)] Of Byte;
Const
  m = 256;
  a: arrType = (44, 55, 12, 42, 94, 18, 6, 67);
  
Procedure RadixSort(Var source, sorted: arrType);
Type indexType = Array[0 .. Pred(m)] Of Byte;
Var
  distr, index: indexType;
  i: integer;
begin
  fillchar(distr, sizeof(distr), 0);
  for i := 0 to Pred(n) do
    inc(distr[source[i]]);
    
  index[0] := 0;
  for i := 1 to Pred(m) do
    index[i] := index[Pred(i)] + distr[Pred(i)];
    
  for i := 0 to Pred(n) do begin
    sorted[ index[source[i]] ] := source[i];
    index[source[i]] := index[source[i]]+1;
  end;
end;

var b: arrType;

begin
  RadixSort(a, b);
end.
Ребят как правильно его на асме реализовать? Ума не приложу! Помогите бедному студенту позязя!
Cobalt вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализация сортировки Шелла beginner Помощь студентам 7 24.05.2015 23:47
реализация сортировки в файле zomba Помощь студентам 1 20.07.2012 12:12
STL реализация алгоритма сортировки в классе Progsenya Общие вопросы C/C++ 0 09.09.2010 21:36
Помогите разобраться в реализации поразрядной сортировки(код внутри) CooCkoo Помощь студентам 0 15.06.2009 23:52
Реализация сортировки по нескольким полям mrMoRiC Общие вопросы C/C++ 1 23.02.2009 18:49