決策表快速排序：屬性序下的粗糙集約簡算法實現

編輯：關於C語言

決策表排序是粗糙集理論中屬性約簡的關鍵預處理步驟。本文實現了基於屬性序的快速排序算法，源自《計算機學報》相關研究，在 UCI 數據集上展現優異性能。

問題背景

決策表類似關係數據庫二維表，每行為對象，列為條件屬性+決策屬性。約簡需先對象分類，蠻力兩兩比較 O(n²) 不可行，排序後分類可降至 O(n log n)。

數據示例

原始表：          排序後（按第1列→第2列→第3列）：
4 3 0             1 0 1
1 0 1             1 2 0
8 1 0             1 2 1
1 2 0             4 3 0
1 2 1             7 3 1
7 3 1             7 4 0
7 4 0             8 1 0

算法核心：多鍵值快速排序

遞歸按屬性序排序：先按第 1 屬性分區，再在相等分區內按第 2 屬性排序，以此類推。

關鍵數據結構

typedef struct {
    int *data;           // 扁平化存儲：row * attrs + col
    int rows, cols;      // 行數、屬性數
    int *tblIdx;         // 行索引排序結果
    int *posRegion;      // 正區域標記
} DecisionTable;

分區邏輯（三向切分擴展）

int partition(DecisionTable *dt, int *idx, int stage, int low, int high) {
    int ext = dt->cols;
    int *data = dt->data;
    int mid = low, hiEnd = mid + 1;
    int pivot = data[idx[low] * ext + stage];
    int counter = 0;
    
    for (int i = low + 1; i <= high; i++) {
        int val = data[idx[i] * ext + stage];
        if (val < pivot) {
            swap(&idx[mid++], &idx[i]);
            hiEnd++;
            counter++;
        } else if (val == pivot) {
            swap(&idx[hiEnd++], &idx[i]);
        }
    }
    swap(&idx[low], &idx[mid]);
    return mid;  // 返回 =pivot 區域邊界
}

遞歸多維排序

void TDQuicksort(DecisionTable *dt, int *idx, int stage, int low, int high) {
    if (stage >= dt->condAttrs || low >= high) return;
    
    int mid = partition(dt, idx, stage, low, high);
    int nextStage = stage + 1;
    
    // 處理  1)  // 多於1個元素才需下一層排序
            TDQuicksort(dt, idx, nextStage, i, j-1);
        i = j;
    }
    
    // 處理 >pivot 區域
    TDQuicksort(dt, idx, stage, mid + 1, high);
}

正區域計算

排序後，相同條件屬性的對象連續分布。掃描判斷決策屬性是否一致，標記正區域。

void loadPositiveRegion(DecisionTable *dt, int *idx, int *posRegion) {
    // 使用堆內存管理條件類
    // 比較條件屬性相同的連續塊，決策屬性一致則標記為正區域
    // 位運算優化：將多屬性打包為 BigInt 比較
}