Реализации алгоритмов/Сортировка/Поразрядная

C++

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

Lua

local function list_to_buckets(array, base, iteration)
    local buckets = {}
    for i=1,base do 
        buckets[i]={}
    end
    for _, number in pairs(array) do
        -- определение значения текущего разряда числа
        local digit = math.floor((number / math.pow(base, iteration))) % base+1
        -- добавить число в контейнер с такими же значениями разряда
        table.insert(buckets[digit],number)
    end
    return buckets
end

local function buckets_to_list(buckets)
    local numbers = {}
    -- добавление в возвращаемый массив из каждого разряда ...
    for _, bucket in pairs(buckets) do
        -- ... каждого числа
        for _, number in pairs(bucket) do
            table.insert(numbers,number)
        end
    end
    return numbers
end

function max(array)
    local m=array[1]
    for i=2,#array do
        if array[i]>m then 
          m=array[i]
        end
    end
    return m
end

function radix_sort(array, base)
    local base=base or 10
    local maxval = max(array)
    local it = 0
    while math.pow(base, it) <= maxval do
        array = buckets_to_list(list_to_buckets(array, base, it))
        it = it + 1
    end
    return array
end

C#

//Поразрядная сортировка с поддержкой отрицательных чисел
public class RadixSort
{
   public static long[] SortL(long[] arr)
   {
       if (arr == null || arr.Length == 0)
           return arr;

       int i, j;
       var tmp = new long[arr.Length];
       for (int shift = sizeof(long)*8 - 1; shift > -1; --shift)
       {
           j = 0;
           for (i = 0; i < arr.Length; ++i)
           {
               var move = (arr[i] << shift) >= 0;
               if (shift == 0 ? !move : move)
                   arr[i - j] = arr[i];
               else
                   tmp[j++] = arr[i];
           }
           Array.Copy(tmp, 0, arr, arr.Length - j, j);
       }

       return arr;
   }        
}

//Юнит-тест
[Theory]
[InlineData(new long[] { })]
[InlineData(new long[] { 1 })]
[InlineData(new long[] { long.MaxValue, 1, 2, 3, long.MinValue })]
[InlineData(new long[] { 1, 1, 1 })]
[InlineData(new long[] { 3, 2, int.MaxValue, 3 })]
[InlineData(new long[] { 3, 2, 1 })]
[InlineData(new long[] { 1, 2, 3, 1 })]
[InlineData(new long[] { -1, 123, 5, 7, 4000, 8, 567, 987, 311, 900, 0, -1 })]
[InlineData(new long[] { -1, 123, 5, 7, 4000, 8, 567, 987, 311, 900, 0, -1, 311 })]
[InlineData(new long[] { 1, 5, 1, 2, 10, 6, 9, 8, 3, 7, 4 })]
[InlineData(new long[] { 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4 })]
public void Test(long[] arr)
{
   var res = RadixSort.SortL((long[])arr.Clone());

    Assert.Equal(arr.OrderBy(x => x), res);
}