珠排序

珠排序係一種自然排序演算法，係Joshua J. Arulanandham、Cristian S. Calude、Michael J. Dinneen嚮2002年發明嘅，喺歐洲理論電腦科學協會（European Association for Theoretical Computer Science）嘅新聞簡報度發表過。唔理係用數碼定係類比嘅硬體嚟做珠排序，都係用O(n)嘅時間就搞掂，不過，一改用軟體嚟做嘅話就會慢咗好多。呢種方法淨係可以直接用嚮非負整數嘅資料度，如果無特殊處理係排唔到負數、定點小數或者浮點小數嘅。就算嚮最理想嘅情況下，至少都要O(n²)嘅空間。

概要

珠排序需要一個特製嘅類似算盤噉樣嘅裝置，係實物嘅或者用電腦模擬嘅都得，擧個例，將下面呢五個數由細到大排好：

2	4	1	3	3

開始嗰陣要將個裝置打平放，方便好似右上圖一樣將算珠排好，喺最頂嗰列擺兩粒珠代表頭一個數字「2」，喺佢下面嗰列擺四粒珠代表第二個數字「4」，如此類推，直到代表每個數字嘅珠仔都擺好嗮為止，啲珠通常都會全部靠向同一邊咁排嘅。

跟住就將個裝置靠向第一列嘅一邊搦起，等啲珠自己滑落，直到所有算珠嘅下底嗰列都填滿為止（除咗墊底嗰一列），就會好似右下圖噉樣。家陣由最頂嗰列開始睇：

1	2	3	3	4

每一列算珠嘅數目正正就等如嗰五個數由細到大排嘅結果。

由於重力嘅作用，下底無承托嘅算珠會向下跌，直到碰到嚮佢下面嗰粒珠或者跌到底嗰列為止。因為大啲嘅數有多啲珠，細啲嘅數就少啲，所以多出嚟嘅珠一定會跌落去，噉就做到越大嘅數越沉底，越細嘅數就越浮面嘅情況。

複雜度

對應唔同嘅做法，珠排序嘅複雜度都有唔同：

做法	複雜度	說明
思想實驗式	O( $1$ )	所有算珠同時瞬間移動，嚮現實中係無法實現嘅。
物理機械式	O( ${\sqrt {n}}$ )	喺重力作用下，算珠下跌嘅時間同算珠嘅高度嘅平方根成正比，呢個高度同數列長度n成正比。
電子硬體式	O( $n$ )	無論係數碼定係類比型式嘅硬體，啲算珠都係逐行逐行噉搬，所以用嘅時間同n成正比。
電腦軟體式	O( $S$ )	S係算珠嘅總數（等如數列嘅總和），因為軟體要逐粒珠去搬，所以時間複雜度同S成正比。

改良版

電腦軟體式嘅珠排序可以改良，假設數列 $L$ 有 $n$ 個非負整數 $i_{j}:1\leq j\leq n$ ，先搵出最細嗰個數 $i_{min}$ ，然後將每個數 $i_{j}$ 都減 $i_{min}$ ，得到一個新數列 $L_{opt}$ ，以珠排序排列 $L_{opt}$ ，可以將複雜度由O( $S$ )改良為O( $S-ni_{min}$ )。最後將 $L_{opt}$ 還原返做 $L$ 就搞掂嘞。

呢個版本重可以令珠排序處理到負整數，代價係用多咗時間同空間，因為 $i_{min}$ 係負數， $S-ni_{min}>S$ 。

C++嘅實例

呢個例子利用C++嘅標準模板庫（Standard Template Library）裏面嘅「位元集」（bitset）嚟模擬算珠，係「改良版」，可以排負整數、字元（char）。程式用C++14標準語法嚟寫，編譯嗰陣可能要加選項，例如GNU C++要加「-std=c++14」。

Bead Sort

#include <cstdlib>
#include <bitset>
#include <string>
#include <algorithm>
#include <ctime>
#include <iostream>

using namespace std;

typedef unsigned int DEFTYPE;  // Default data type (should be integral types)
size_t constexpr DEFBEADS = 256U;  // Default no. of beads (per row)

template<typename Type=DEFTYPE, size_t Beads=DEFBEADS>
class BeadSort
{
  public:
    enum class Order : unsigned int { ascending, descending };
  private:
    Order          order;
    bitset<Beads>* beads;
    typedef typename bitset<Beads>::reference bead;
    auto beadsort (size_t const, Type const) -> void;
    auto freefall (bead, bead) -> bead const;
  public:
    explicit BeadSort (void);
    auto sort (Type [], size_t const, Order const = Order::ascending) -> void;
    ~BeadSort (void);
  // Make objects of this class non-copyable
    BeadSort (BeadSort const&) = delete;
    BeadSort& operator = (BeadSort const&) = delete;
};
 
// Disallow floating-point data types by partial template specialization
template<size_t Beads> class BeadSort<float, Beads> { };
template<size_t Beads> class BeadSort<double, Beads> { };
template<size_t Beads> class BeadSort<long double, Beads> { };

// Class default constructor
template<typename Type, size_t Beads>
BeadSort<Type, Beads>::BeadSort (void) : order(Order::ascending), beads(nullptr) { return; }

// Sort array 'arr' of size 'size' in type 'Type' into 'order' order
template<typename Type, size_t Beads>
auto BeadSort<Type, Beads>::sort (Type arr[], size_t const size, Order const order) -> void
{
  Type const minnum = *min_element(arr, arr + size);
  
  this->order = order;
  this->beads = new(nothrow) bitset<Beads>[size];
  
  if (beads)
  { // Optimize, also ensure all nos. are non -ve
    transform(arr, arr + size, arr,
      [minnum](Type const n) -> Type const { return n - minnum; });
    // Turn nos. into beads
    transform(arr, arr + size, beads,
      [](Type const n) -> bitset<Beads> { return bitset<Beads>(string((size_t)n, '1')); });
    // Sort array by bead sort
    beadsort(size, *max_element(arr, arr + size));
    // Turn beads into nos.
    transform(beads, beads + size, arr,
      [](bitset<Beads> const& n) -> Type const { return (Type)n.count(); });
    // Restore the nos. to original
    transform(arr, arr + size, arr,
      [minnum](Type const n) -> Type const { return n + minnum; });
    
    delete [] beads;
  }
  else  // Abort on fatal error
    cerr << "Memory allocation failure." << endl, exit(EXIT_FAILURE);
  
  return;
}

// Implement the beadsort algorithm
template<typename Type, size_t Beads>
auto BeadSort<Type, Beads>::beadsort (size_t const size, Type const maxnum) -> void
{
  size_t const totalrows = size - 1;
  size_t const totalcols = (size_t)maxnum;
  bool   const ascending = order == Order::ascending;  // Sort in ascending order?
  size_t nextrow[totalcols];  // Point to next row where to start looking for a bead
  
  fill(nextrow, nextrow + totalcols, (size_t)1);  // Start looking in 2nd row of each column
  
  for (size_t thisrow = 0, thatrow = 0; thisrow < totalrows; ++thisrow)
    for (size_t curcol = 0; curcol < totalcols; ++curcol)
      if (!beads[thisrow][curcol] ^ ascending)  // Is this a blank?
        for (thatrow = nextrow[curcol]; thatrow <= totalrows; ++thatrow)
          if (beads[thatrow][curcol] ^ ascending)  // Is that a bead?
          { // Found a bead in that row, so let it fall freely to this row
            freefall(beads[thatrow][curcol], beads[thisrow][curcol]);
            nextrow[curcol] = thatrow + 1;
            break;  // Next column
          }
          else
            ++nextrow[curcol];
      else
        ++nextrow[curcol];
  
  return;
}

// Imitate the free fall of a bead
template<typename Type, size_t Beads>
auto BeadSort<Type, Beads>::freefall (bead from, bead to) -> bead const
{
  return to = ~from.flip();
}

// Class destructor
template<typename Type, size_t Beads>
BeadSort<Type, Beads>::~BeadSort (void) { return; }

// Generate a random no. in the range [0, Beads)
template<typename Type, size_t Beads>
auto random (void) -> Type const
{
  return (Type)((size_t)rand() % Beads);
}

// Conduct a test case
template<typename Type=DEFTYPE, size_t Beads=DEFBEADS>
auto testcase (size_t const size, typename BeadSort<Type, Beads>::Order order,
        Type const offset) -> void
{
  char const static* const orders[] = {"ascending", "descending"};
  Type                     arr[size];
  BeadSort<Type, Beads>    beadsort;
  
  // Generate test case at random
  generate(arr, arr + size, random<Type, Beads>);
  // Apply optional offset to nos.
  transform(arr, arr + size, arr, [offset](Type const n) { return n + offset; });
  // Show unsorted list
  for_each(arr, arr + size, [](Type const n) { cout << ' ' << n; }), cout << endl;
  // Sort the list
  beadsort.sort(arr, size, order);
  cout << "sorted in " << orders[(size_t)order] << " order:" << endl;
  // Show sorted list
  for_each(arr, arr + size, [](Type const n) { cout << ' ' << n; }), cout << endl << endl;
  
  return;
}

auto main (int const argc, char const* const* const argv) -> int
{
  srand((unsigned int)time(nullptr));
  // Case 1: sort 10 unsigned integers in descending order
  testcase<>(10, BeadSort<>::Order::descending, 0U);
  // Case 2: sort 12 signed integers in ascending order
  testcase<int>(12, BeadSort<int>::Order::ascending, -random<int, 100>());
  // Case 3: sort 15 uppercase letters in ascending order
  testcase<char, 26>(15, BeadSort<char, 26>::Order::ascending, 'A');
  
  return EXIT_SUCCESS;
}

/********* Sample output **********\
 208 248 136 106 0 188 129 250 37 13
sorted in descending order:
 250 248 208 188 136 129 106 37 13 0

 8 -22 0 -6 13 -64 20 64 -12 31 -9 -46
sorted in ascending order:
 -64 -46 -22 -12 -9 -6 0 8 13 20 31 64
 
 W H N X R A H Z P U O P B M P
sorted in ascending order:
 A B H H M N O P P P R U W X Z
\**********************************/

睇埋

出面網頁

The Bead Sort paperPDF (114 KiB)
Bead Sort in MGS, a visualization of a bead sort implemented in the MGS programming language
Bead Sort on MathWorld