K.Maebashi's BBS

話の腰を揉んでみるテスト。ふにふに >リンクリストは、要素(サンプルの場合、list)を削除する処理が >配列に比べて早いというのが一般的に言われています。 リストを使う理由としては、配列だと削除された要素の後ろの要素を指すイテレータの扱いに困る、というのもありますね。 STLではそういうイテレータは無効になります。 >また、ソートに関しては基本的にリンクリストより配列の方が早いと思います。 >と言うのも、例えばクイックソートを使うならランダムアクセスが必要になるので >そもそもリンクリストでは(クイックソートは)無理です。 クイックソートは、アルゴリズムそのものにはランダムアクセスは不要です。 ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 実装はリンクリストの方がむしろ簡単だと思います。 void quick_sort(Node ** head_p) { if (*head_p != NULL && (*head_p)->next != NULL) { Node *p; Node *left = NULL, *right = NULL; Node **left_p = &left, **right_p = &right; for (p = (*head_p)->next; p != NULL; p = p->next) { if (p->value < (*head_p)->value) { *left_p = p; left_p = &(*left_p)->next; } else { *right_p = p; right_p = &(*right_p)->next; } } *left_p = *right_p = NULL; quick_sort(&left); quick_sort(&right); for (; *left_p != NULL; left_p = &(*left_p)->next) ; *left_p = *head_p, (*head_p)->next = right; *head_p = left; } } ＃ いや、ループが1重で済んでるし＜簡単