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

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


[ 湯会老人の説明 ]

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

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

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

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

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 の性能がデータ依存になるのはこのためでしょう。

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

[ 0325: 最悪ケースでの sort 比較 ]

[ 0324: 0307の回答 ④ ]

[ 0323: 0307の回答 ③ ]

[ 0322: 0307の回答 ② ]

[ 0321: 0307の回答 ① ]

[ 0320: 前の記事 ]

[ トップページへ ]