Radix sort, MSD. Для char-строк. Ноль - конец строки. На основе рекурсии. Глубина рекурсии = длина строки + 1. В каждой рекурсии требуется память для размещения двух массивов указателей: StringItem* front[256], т.е. 2Кб;

//элемент списка
struct StringItem{
  const char* str; //указатель на строку
  StringItem* next;
};
 
//pList - начало списка указателей на строки
//iDigit - разряд, по которому сортирует
//возвращает указатель на первый элемент отсортированной последовательности
StringItem*  radix_sort_msd_for_string(StringItem* pList, unsigned int iDigit )
{
  // количество вариантов значения одного разряда (char)
  const int iRange = 256; 
 
  //массив bucket-ов (под-списков)
  StringItem* front[iRange]; 
  memset(front, 0, sizeof(front) );
 
  StringItem** ppNextItem[iRange]; 
  for (int i = 0; i < iRange; i++)
    ppNextItem[i]=&front[i];
 
  //разбиваем список на bucket-ты, в зависимости от значения разряда
  while (pList)
  {
    StringItem* temp = pList;
    pList=pList->next;
 
    temp->next=NULL; //отключаем от списка
 
    unsigned char c = (unsigned char)temp->str[iDigit];
    *ppNextItem[c]=temp;
    ppNextItem[c]=&temp->next;
  }
 
  //строим выходной список
  StringItem* pResult = NULL;
  StringItem** ppNext = &pResult;
 
  //нулевой bucket возвращаем весь - он уже отсортирован
  *ppNext = front[0];
  while (*ppNext)
    ppNext=&((*ppNext)->next);
 
  for (int i = 1; i < iRange; i++)
  {
    //пустые - пропускаем
    if ( !front[i] )
      continue;
 
    if (front[i]->next == NULL)// с одним элементом - сразу добавляем
      *ppNext = front[i];
    else    // остальные - на сортировку по следующему разряду
      *ppNext = radix_sort_msd_for_string(front[i], iDigit + 1);
 
    while (*ppNext)
      ppNext=&((*ppNext)->next);
  }
 
  return pResult;}

Программа для тестирования

void TestAlgorithm()
{
  // открываем, большой текстовый файл для теста
  ifstream file("demo.txt"); 
  if ( !file )
    return;
 
  //считываем все слова из файла в вектор
  istream_iterator<string> ii(file);
  istream_iterator<string> eos;
  vector<string> vecs(ii, eos);
 
  // заполняем список 
  StringItem* pList = NULL;
  StringItem** ppCurr = &pList;
  for ( unsigned int i=0 ; i<vecs.size(); i++)
  {
    *ppCurr = new StringItem();
    (*ppCurr )->str = vecs[i].c_str();
    (*ppCurr )->next = NULL;
    ppCurr = &(*ppCurr)->next;    
  }
 
  //сортируем
  pList = radix_sort_msd_for_string(pList, 0);
 
  //файл для вывода
  ofstream fo("out.txt");
  ostream_iterator<string> oo(fo," ");
 
  // в конце удаляем список
  while(pList)
  {
    oo = pList->str; // выводим в файл
    StringItem* tmp = pList;
    pList = pList->next;
    delete tmp;
  }
}

Вариант сортировки 32 битных unsigned int. Не самый быстрый.

void radix_int(unsigned* begin, int size, unsigned bit = 0x80000000)
{
    if (!bit)
        return;
 
    if (size < 2)
        return;
 
    int last = 0;
    for (int i = 0; i < size; i++)
    {
        if ((begin[i] & bit) == 0)
            swap(begin[last++], begin[i]);
    }
 
    radix_int(begin,      last,      bit >> 1);
    radix_int(begin+last, size-last, bit >> 1);
}

Вариант сортировки 8 битных char. Порядок обратный. Для правильного порядка необходимо копировать сначала нули, потом единицы...

int radix_8(char* bytes, const int bcount)
{
        char* oneArray = (char*)malloc(bcount);
        char* zeroArray = (char*)malloc(bcount);
        int numOnes;
        int numZeros;
 
        int mask = 1;
 
        for (int count = 0; count < 8; count++)
        {
                numOnes = 0;
                numZeros = 0;
 
                for (int index = 0; index < bcount; index++)
                {
                        char bt = bytes[index];
                        if (bt & mask)
                        {
                                oneArray[numOnes] = bt;
                                numOnes++;
                        }
                        else
                        {
                                zeroArray[numZeros] = bt;
                                numZeros++;
                        }
                }
 
                // копирование единиц
                memcpy(bytes, oneArray, numOnes);
 
                // копирование нолей
                memcpy(bytes + numOnes, zeroArray, numZeros);
 
                // изменение маски для проверки следующего бита
                mask <<= 1;
        }
        free(oneArray);
        free(zeroArray);
}

Добавлено: 29 Мая 2018 20:21:52 Добавил: Андрей Ковальчук Нравится 0

Добавить