Можете ли вы сформулировать моноид или полугруппу для радикальной сортировки?

Question

Это псевдокод для радикальной сортировки:

Pseudocode for Radix Sort:
Radix-Sort(A, d)
// Each key in A[1..n] is a d-digit integer. (Digits are
// numbered 1 to d from right to left.)
1. for i = 1 to d do
Use a stable sorting algorithm to sort A on digit i.

Это код Scala для радикальной сортировки:

object RadixSort {
  val WARP_SIZE = 32

  def main(args: Array[String]) = {
    var A = Array(123,432,654,3123,654,2123,543,131,653,123)

    radixSortUintHost(A, 4).foreach(i => println(i))
  }

  // LSB radix sort
  def radixSortUintHost(A: Array[Int], bits: Int): Array[Int] = {
    var a = A
    var b = new Array[Int](a.length)

    var rshift = 0
    var mask = ~(-1 << bits)

    while (mask != 0) {
      val cntArray = new Array[Int](1 << bits)

      for (p <- 0 until a.length) {
        var key = (a(p) & mask) >> rshift
        cntArray(key)+= 1
      }

      for (i <- 1 until cntArray.length)
        cntArray(i) += cntArray(i-1)

      for (p <- a.length-1 to 0 by -1) {
        var key = (a(p) & mask) >> rshift
        cntArray(key)-= 1
        b(cntArray(key)) = a(p)
      }

      val temp = b
      b = a
      a = temp

      mask <<= bits
      rshift += bits
    }

    b
  }
}

Это код Haskell для сортировки по основанию:

import Data.Bits (Bits(testBit, bitSize))
import Data.List (partition)

lsdSort :: (Ord a, Bits a) => [a] -> [a]
lsdSort = fixSort positiveLsdSort

msdSort :: (Ord a, Bits a) => [a] -> [a]
msdSort = fixSort positiveMsdSort

-- Fix a sort that puts negative numbers at the end, like positiveLsdSort and positiveMsdSort
fixSort sorter list = uncurry (flip (++)) (break (< 0) (sorter list))

positiveLsdSort :: (Bits a) => [a] -> [a]
positiveLsdSort list = foldl step list [0..bitSize (head list)] where
step list bit = uncurry (++) (partition (not . flip testBit bit) list)

positiveMsdSort :: (Bits a) => [a] -> [a]
positiveMsdSort list = aux (bitSize (head list) - 1) list where
aux _ [] = []
aux (-1) list = list
aux bit list = aux (bit - 1) lower ++ aux (bit - 1) upper where
    (lower, upper) = partition (not . flip testBit bit) list

Мой вопрос: можете ли вы сформулировать моноид или полугруппу для радикальной сортировки?

Answer 1

Инвариант радикальной сортировки состоит в том, что данные сортируются с использованием первых k битов. Если вы хотите, чтобы операция добавляла больше отсортированных данных или нет, вы запрашиваете функциональность сортировки слиянием, а не основание. Если то, что вы добавляете, это биты данных для всех записей, вы можете использовать моноид.

Редактировать: Харт моноида является ассоциативной операцией. Мы можем рассматривать биты сортировки как способ применения частичного порядка. Вы повреждаете данные для всех записей по крупицам. Каждый бит применяет частичный порядок. Это ассоциативно, вы можете объединить некоторые биты, чтобы получить более сложный частичный порядок. Порядок примечаний важен, но он по-прежнему ассоциативен и поэтому может рассматриваться как монада

Answer 2

Я думаю, что вы, возможно, слишком буквально думаете об идее радикальной сортировки. Абстрактно, я представляю моноид, который вы хотите

1. Сортированные списки с
2. сращивание

Большой вопрос в том, как вы хотите представлять отсортированные списки. Если вы представляете их как отсортированные списки Haskell, то операция слияния - это обычное пошаговое слияние, используемое при сортировке слиянием. Если вы представите их более "радикально", у вас будет несколько вариантов. Вы можете, вероятно, найти некоторые алгоритмы для объединения попыток. Есть один в bytestring-trie, но ничего о его реализации, похоже, не задокументировано.