分段雙調(diào)排序 - Shuai-Xie -Github
問(wèn)題說(shuō)明
給出分成 m 段的 n 個(gè)浮點(diǎn)數(shù)唆铐，輸入數(shù)據(jù)已按段號(hào)有序勋又，但每段內(nèi)部無(wú)序没炒。
用 C/C++ 編寫一個(gè)分段雙調(diào)排序(Bitonic sort)函數(shù)缔俄，對(duì)每一段內(nèi)部的浮點(diǎn)數(shù)進(jìn)行排序个粱，但不要改變段間的位置蝎宇。
1. 接口方式
// 分段雙邊排序
void segmentedBitonicSort(float* data, int* seg_id, int* seg_start, int n, int m);
- data 包含需要分段排序的 n 個(gè) float 值（由下面的 seg_id 可知是表示多段的數(shù)據(jù)）
- seg_id 給出 data 中 n 個(gè)元素各自所在的段編號(hào)
- seg_start 共有 m+1 個(gè)元素畏妖，前 m 個(gè)分別給出 0..m-1 共 m 個(gè)段的起始位置绩聘，seg_start[m] = n
- n 表示 data 中包含 n 個(gè)數(shù)據(jù)
- m 表示 data 分為 m 段數(shù)據(jù)
由題意得亲澡，m <= n钦扭，因?yàn)?data 某一段可能有多于 1 個(gè)數(shù)據(jù)，這種情況下：m < n
seg_id 中的元素保證單調(diào)不下降床绪，即對(duì)任意的 i < j客情，seg_id[i] <= seg_id[j]
seg_id 所有元素均在 0 到 m-1 范圍內(nèi)。（因?yàn)槭嵌?id癞己，m 段就是0..m-1）
2. 輸入輸出
輸入
float data[5] = {0.8, 0.2, 0.4, 0.6, 0.5};
int seg_id[5] = {0, 0, 1, 1, 1}; // 0,1 所在位置元素對(duì)應(yīng)的段id
int seg_start[3] = {0, 2, 5}; // 表示第1段從0開(kāi)始:{0.8, 0.2}膀斋，第2段從2開(kāi)始:{0.4, 0.6, 0.5}
int n = 5; // 總共5個(gè)數(shù)
int m = 2; // 2段
輸出
float data[5] = {0.2, 0.8, 0.4, 0.5, 0.6};
3. 其他要求
3.1 注意
- 必須使用雙調(diào)排序算法進(jìn)行排序。
- 可以直接使用從網(wǎng)上下載的雙調(diào)排序代碼痹雅，但須注明出處仰担。
3.2 加分挑戰(zhàn)（非必需）
- 不遞歸：segmentedBitonicSort 函數(shù)及其所調(diào)用的任何其他函數(shù)都不得直接或間接地進(jìn)行遞歸。
- 不調(diào)用函數(shù)：segmentedBitonicSort 不調(diào)用除標(biāo)準(zhǔn)庫(kù)函數(shù)外的任何其他函數(shù)绩社。
- 內(nèi)存高效：segmentedBitonicSort 及其所調(diào)用的任何其他函數(shù)都不得進(jìn)行動(dòng)態(tài)內(nèi)存分配摔蓝，包括malloc赂苗、new和靜態(tài)定義的STL容器。
- 可并行：segmentedBitonicSort 涉及到的所有時(shí)間復(fù)雜度O(n)以上的代碼都寫在for循環(huán)中贮尉，而且每個(gè)這樣的for循環(huán)內(nèi)部的循環(huán)順序可以任意改變拌滋，不影響程序結(jié)果。注：自己測(cè)試時(shí)可以用rand()決定循環(huán)順序绘盟。
- 不需內(nèi)存：segmentedBitonicSort 不調(diào)用任何函數(shù)（包括C/C++標(biāo)準(zhǔn)庫(kù)函數(shù)）鸠真， 不使用全局變量，所有局部變量都是int龄毡、float或指針類型吠卷，C++程序不使用new關(guān)鍵字。
- 絕對(duì)魯棒：在輸入數(shù)據(jù)中包含 NaN 時(shí)（例如
sqrt(-1.0))沦零，保證除NaN以外的數(shù)據(jù)正確排序祭隔，NaN的個(gè)數(shù)保持不變。
NaN路操，是 Not a Number 的縮寫疾渴。
NaN 用于處理計(jì)算中出現(xiàn)的錯(cuò)誤情況，比如 0.0 除以 0.0 或者求負(fù)數(shù)的平方根屯仗。
你的程序每滿足以上的一個(gè)條件都可以獲得額外的加分搞坝。
3.3 應(yīng)提交的結(jié)果
- 算法描述；
- 嘗試過(guò)和完成了的加分挑戰(zhàn)魁袜；
- 可以獨(dú)立運(yùn)行的源代碼桩撮；
- 測(cè)試數(shù)據(jù)；
- 性能分析峰弹；
- 測(cè)試的起始和完成時(shí)間以及實(shí)際使用的時(shí)間店量。
3.4 提示
- 利用好網(wǎng)上資源。
- 盡量利用輸入中的冗余信息鞠呈。
- 利用好位操作融师。 （>>1）
解答
1. 遞歸分段雙調(diào)排序
#include <iostream>
#include <iomanip>
using namespace std;
/**
* @param arr 小數(shù)數(shù)列
* @param len 數(shù)列長(zhǎng)度
* @param w 輸出單個(gè)小數(shù)的長(zhǎng)度
* @param precision 小數(shù)的精度
*/
void printFloatArr(float *arr, int len) {
for (int i = 0; i < len; ++i) {
cout << setw(4) << arr[i];
}
cout << endl;
}
int getGreatest2nLessThan(int len) {
int k = 1;
while (k < len) k = k << 1; // 注意一定要加k=
return k >> 1;
}
// 任意雙調(diào)排序歸并
void bitonicMergeAnyN(float *arr, int len, bool asd = true) {
if (len > 1) {
int m = getGreatest2nLessThan(len);
for (int i = 0; i < len - m; ++i) {
if (arr[i] > arr[i + m] == asd)
swap(arr[i], arr[i + m]); // 根據(jù)asd判斷是否交換
}
bitonicMergeAnyN(arr, m, asd); // 一般情況下，m > len-m
bitonicMergeAnyN(arr + m, len - m, asd);
}
}
// 雙調(diào)排序
void bitonicSort(float *arr, int len, bool asd) { // asd 升序
if (len > 1) {
int m = len / 2;
bitonicSort(arr, m, !asd); // 前半降序
bitonicSort(arr + m, len - m, asd); // 后半升序
bitonicMergeAnyN(arr, len, asd);
}
}
/**
* 分段雙調(diào)排序
* @param data 原始數(shù)據(jù)
* @param seg_id data 中 n 個(gè)元素各自所在的段編號(hào)
* @param seg_start 共有 m+1 個(gè)元素蚁吝，前 m 個(gè)分別給出 0..m-1 共 m 個(gè)段的起始位置旱爆，seg_start[m] = n
* @param n data 中包含 n 個(gè)數(shù)據(jù)
* @param m data 分為 m 段數(shù)據(jù)
*/
void segmentedBitonicSort(float *data, int *seg_id, int *seg_start, int n, int m) {
bool asd = true;
for (int i = 0; i < m; ++i) {
float *arr = data + seg_start[i]; // 數(shù)列起點(diǎn)
int len = seg_start[i + 1] - seg_start[i]; // 數(shù)列長(zhǎng)度
bitonicSort(arr, len, asd);
cout << "段 " << i << ": ";
printFloatArr(arr, len);
}
}
int main() {
float data[7] = {0.8, 0.2, 0.4, 0.6, 0.5, 0.2, 0.1}; // 數(shù)列
int seg_id[7] = {0, 0, 1, 1, 1, 2, 2}; // id
int seg_start[4] = {0, 2, 5, 7}; // 段首位置
int n = 7; // 數(shù)據(jù)長(zhǎng)度
int m = 3; // 數(shù)據(jù)段數(shù)
segmentedBitonicSort(data, seg_id, seg_start, n, m);
}
段 0: 0.2 0.8
段 1: 0.4 0.5 0.6
段 2: 0.1 0.2
2. 解決NaN問(wèn)題
在歸并的時(shí)候，遇到NaN型數(shù)據(jù)窘茁，就直接跳到下一個(gè)數(shù)據(jù)疼鸟。
// 任意雙調(diào)排序歸并
void bitonicMergeAnyN(float *arr, int len, bool asd = true) {
if (len > 1) {
int m = getGreatest2nLessThan(len);
for (int i = 0; i < len - m; ++i) {
// 解決NaN問(wèn)題
int low = i;
while (arr[low] == NaN) low++;
int high = i + m;
while (arr[high] == NaN) high++;
// 核心代碼
if (arr[low] > arr[high] == asd)
swap(arr[low], arr[high]); // 根據(jù)asd判斷是否交換
}
bitonicMergeAnyN(arr, m, asd); // 一般情況下，m > len-m
bitonicMergeAnyN(arr + m, len - m, asd);
}
}
完整代碼
#include <iostream>
#include <iomanip>
#include <cmath>
#define NaN (float)sqrt(-1.0)
using namespace std;
/**
* @param arr 小數(shù)數(shù)列
* @param len 數(shù)列長(zhǎng)度
* @param w 輸出單個(gè)小數(shù)的長(zhǎng)度
* @param precision 小數(shù)的精度
*/
void printFloatArr(float *arr, int len) {
for (int i = 0; i < len; ++i) {
if (arr[i] == NaN) cout << setw(5) << "NaN";
else cout << setw(5) << arr[i];
}
cout << endl;
}
int getGreatest2nLessThan(int len) {
int k = 1;
while (k < len) k = k << 1; // 注意一定要加k=
return k >> 1;
}
// 任意雙調(diào)排序歸并
void bitonicMergeAnyN(float *arr, int len, bool asd = true) {
if (len > 1) {
int m = getGreatest2nLessThan(len);
for (int i = 0; i < len - m; ++i) {
// 解決NaN問(wèn)題
int low = i;
while (arr[low] == NaN) low++;
int high = i + m;
while (arr[high] == NaN) high++;
if (arr[low] > arr[high] == asd)
swap(arr[low], arr[high]); // 根據(jù)asd判斷是否交換
}
bitonicMergeAnyN(arr, m, asd); // 一般情況下庙曙，m > len-m
bitonicMergeAnyN(arr + m, len - m, asd);
}
}
// 雙調(diào)排序
void bitonicSort(float *arr, int len, bool asd) { // asd 升序
if (len > 1) {
int m = len / 2;
bitonicSort(arr, m, !asd); // 前半降序
bitonicSort(arr + m, len - m, asd); // 后半升序
bitonicMergeAnyN(arr, len, asd);
}
}
/**
* 分段雙調(diào)排序
* @param data 原始數(shù)據(jù)
* @param seg_id data 中 n 個(gè)元素各自所在的段編號(hào)
* @param seg_start 共有 m+1 個(gè)元素空镜，前 m 個(gè)分別給出 0..m-1 共 m 個(gè)段的起始位置，seg_start[m] = n
* @param n data 中包含 n 個(gè)數(shù)據(jù)
* @param m data 分為 m 段數(shù)據(jù)
*/
void segmentedBitonicSort(float *data, int *seg_id, int *seg_start, int n, int m) {
bool asd = true;
for (int i = 0; i < m; ++i) {
float *arr = data + seg_start[i];
int len = seg_start[i + 1] - seg_start[i];
bitonicSort(arr, len, asd);
cout << "段 " << i << ": ";
printFloatArr(arr, len);
}
}
int main() {
float data[11] = {0.8, 0.2, 0.4, NaN, 0.6, 0.5, NaN, 0.2, 0.1, NaN, 0.01}; // 數(shù)列
int seg_id[11] = {0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2}; // id
int seg_start[4] = {0, 2, 6, 11}; // 段首位置
int n = 11; // 數(shù)據(jù)長(zhǎng)度
int m = 3; // 數(shù)據(jù)段數(shù)
segmentedBitonicSort(data, seg_id, seg_start, n, m);
}
段 0: 0.2 0.8
段 1: 0.4 NaN 0.5 0.6
段 2: NaN 0.01 0.1 NaN 0.2
