ソートについて

[sato]

最近プログラミングコンテストに参加しようと勉強を始めたのですが、ソートについて分からないことがあります。
ソートについて調べていると、配列などに入っている値をソートするというプログラムはよくあるのですが、ほかの値も一緒に並べ替えるにはどうしたらよいのでしょうか。
たとえば、テストの点数から成績順に学籍番号を並べ替えたいなどの場合です。

言語はC/C++でお願いします。ただ、STLについてはまだまだ未熟なので難しいことは全くわかりません。よろしくお願いします。

[usao]

>たとえば、テストの点数から成績順に学籍番号を並べ替えたいなどの場合です。

コード:

struct StudentData
{
  int TestScore;  //テストの点
  int StudentID;  //学籍番号
};

のようなデータの配列を作ってソートすればどうでしょうか．
もし，↓のようにデータを持っているとしたら…

コード:

const int N = 10;
int TestScore[N] = { ... };
int StudentID[N] = { ... };

ソート処理により動かすものをTestScore[]等のデータそのものではなく　配列のindex値にする　とかすればよいのではないでしょうか．

[sato]

やや言葉足らずだったようで申し訳ありません。できればソートアルゴリズムは自分で実装せずに他のライブラリから呼び出して使いたいと考えているのですが、その方法がわかりません。自分で書こうとしても、高速なアルゴリズムにするには時間がかかってしまうので、あまり現実的ではない気がします。

[みけCAT]

構造体にデータを入れて、qsort関数（stdlib.h）を使うといいと思います。
ググってみてください。
[search=google]qsort 構造体[/search]

[usao]

やや言葉足らずだったようで申し訳ありません。できればソートアルゴリズムは自分で実装せずに他のライブラリから呼び出して使いたいと考えているのですが、その方法がわかりません。自分で書こうとしても、高速なアルゴリズムにするには時間がかかってしまうので、あまり現実的ではない気がします。

処理方針(?)を示しただけです．
ソートアルゴリズム部分は std::sort なりなんなりを使えばよいのではないでしょうか．

[softya（ソフト屋)]

闇雲にソートしても効率が良いかは分からないので知識が必要です。
１００件程度のデータにクイックソートは逆に遅いです。
「ソート時間の比較」
http://www.ics.kagoshima-u.ac.jp/~fuchi ... mpare.html

[sato]

>> みけCAT様
qsort関数というのは知りませんでした。構造体をこんな簡単にソートできるという関数があるとは。ぜひ使ってみます。

>>usao様
std::sortも考えたのですが、質問のような処理をすることができるのかすら分かりませんでした。STLについてはまだ未知の領域なのでこれから開拓していきたいと思います。

>>softya様
少ないデータ数ではクイックソートもずいぶん遅いですね。逆に単純なバブルソートがそこそこの速度を出すというのは不思議です。参考にさせていただきます。


皆様回答ありがとうございました。