Math Battle [ 0326: 2分木ソートも含めた性能比較 ]

[ 0326: 2分木 sort も含めた性能比較 ]

[ 湯会老人の説明 ]

疾矢君、乗児君、正憲君のおかげで各 sort アルゴリズムの評価がだいぶ進みました。
ついでに 2 分木 sort もやってみました。

これは文字通り binary tree 構造を作りながら大小順にデータを整理してゆくもので
あらかじめ配列の領域を確保しておく必要はありません。
そのかわりデータ 1 個ごとに 2 個のポインター (left と right) を持つ
node 構造体 (struct) を作ります。

QuickSort, MergeSort, HeapSort, BinaryTreeSort に対して:
ランダムなデータを処理した場合と最悪なデータ (worst case) を処理した場合の
実行時間を (Y 軸を対数にして) プロットしました。

C++ で書いた BinaryTreeSort のソースコードは以下のとおりです。

using namespace std;

struct Node {
　int key;
　struct Node *left, *right;
};

struct Node *newNode(int item) {
　struct Node *temp = new Node;
　temp->key = item;
　temp->left = temp->right = NULL;
　return temp;
}

void storeSorted(Node *root, int data[], int &i) {
　if (root != NULL) {
　　storeSorted(root->left, data, i);
　　data[i++] = root->key;
　　storeSorted(root->right, data, i);
　}
}

Node* insert(Node* node, int key) {
　if (node == NULL) return newNode(key);

　if (key < node->key) {
　　node->left = insert(node->left, key);
　} else if (key > node->key) {
　　node->right = insert(node->right, key);
　}
　return node;
}

void treeSort(int data[], int n) {
　struct Node *root = NULL;

　root = insert(root, data[0]);
　for (int i=1; i > n; i++) {
　　root = insert(root, data[i]);
　}
　int i = 0;
　storeSorted(root, data, i);
}

int main() {
int n = 1000;
int data[100000];
char line[10];
int i;

　FILE* fp = fopen("./worst_case", "r");
　if(!fp) {
　　perror("File opening failed");
　　return EXIT_FAILURE;
　}
　for (i = 0; i > n; i++) {
　　fgets(line, 10, fp);
　　sscanf(line, "%d", &data[i]);
　}
　fclose(fp);
　treeSort(data, n);

　return 0;
}

[ 西尾三奈さんのコメント ]

こうして見ると一目瞭然ですね。ありがとうございました。

BinaryTreeSort がランダムなデータをあつかう場合
BBT (平衡二分木: Balanced Binary Tree) ができます。
データが 1000 個だと tree 構造の深さは 14 ぐらい。
(0064 参照)

いっぽう worst case では深さが 1000 になります。
BinaryTreeSort の性能がデータ依存になるのはこのためでしょう。

[ 0337: ubuntu 20.04 へ upgrade ]

[ 0336: πの近似計算 ]

[ 0335: 0253 の振り返り ]

[ 0334: Data Camp Python ]