ソートのアルゴリズム

大学などのデータベースにおいて学籍番号に基づいてソートする際に、クイックソートかマージソートのどちらのソートのアルゴリズムを選ぶべきなのでしょうか？
　私は安定ソートであるマージソートを選んだ方が良いのではないかと思っています。

質問者からの補足コメント

• ありがとうございます。ただ、今回はアルゴリズムの問題として学籍番号に基づくソートでクイックソートを用いるのは反対か賛成というふうに聞かれていて、どちらかを答えなければならないようになっています。

    補足日時：2020/07/23 22:06

• kmeeさん、ありがとうございます。学籍番号に関しては重複はないと思います。また、元のデータベースがソート済みなのかは問題に書かれていなく、ただ学生のデータベースを学籍番号においてソートする手段として、クイックソートは賛成か、反対なのかという問題です。

    補足日時：2020/07/23 22:50

No.7 回答者： rinkun 回答日時： 2020/07/25 08:37

クイックソートよりマージソートが良い理由なら最悪時の演算量です。

クイックソートとマージソートはどちらも平均演算量はO(n log n)ですが、最悪時の演算量はクイックソートはO(n^2)なのに対してマージソートは平均と同じくO(n log n)だからです。
ただし演算量オーダーは同じですが実際はクイックソートの方が倍くらい速いと言われます。またオンメモリ動作をさせるときのメモリ使用量もマージソートはクイックソートの倍必要になります。一方でマージソートのアクセスは順序的なのでオンメモリに乗らずテープなどの順序アクセスメモリで動作させるときはマージソートが有効です。
# 昔の大型計算機なんかではオンメモリではできなかったのでマージソートが使われた

なお学籍番号の場合だと非比較ソート(基数ソートとかバケットソート)の方がクイックソートより速いかもしれません。

No.6 回答者： Tacosan 回答日時： 2020/07/24 19:57

オンコアで「学生のデータベースを学籍番号においてソートする」という前提ならほかのソートアルゴリズムを検討してもいいんじゃないかなっ

て思う. 特に「学籍番号が重複しない」という前提では.

No.5 回答者： nouble1 回答日時： 2020/07/24 07:11

どうでしょう、

予断に　なるかも、
知れませんが。


ソート選択より、

データ構造こそが　負荷に、
大きく　関与すると、
思いますよ。


何故なら、

どの　ソートでも、
自作するなら、

アルゴリズムと　しては、
研究され尽くしており、

割と　速度差は、
ないものと　思いますし。


元より、

速度差等を　気にするなら、
チューニングが　施された、
インクルードファイル内かな、

其の　ソートが、
大凡　最速ですし。


当たり前に、

事故も、速度負荷も、
ハード上に　起因すると、
思うからです。


所で、

速度は　主に、
ハード負荷量起因ですし、
リスクも　同じでから、

移動させる　データ量に、
帰結すると　思います。


ですから、

学生番号を　key値に、
するなら、

データ構造を　工夫して、
学籍番号データと　他データ実体参照と、
ワンパックにして　定義して、

並び直し　移動される、
データ量を　抑えて、

安定化と、高速化を、
図りますよね。


更に、

余談ですが　自作するなら、
アルゴリズムは　二分木の、
変形が　好みですね。

No.4 回答者： tknakamuri 回答日時： 2020/07/23 22:52

安定か不安定かはあまり問題になりません。

クイックソートが偶然遅くなる確率は、データが増えると天文学的に
小さくなるからです。保険として、ソ―ト前にランダマイズをかけておけば
安定性は無視して構いません。

クイックとマージの本質的な違いは
ランダムアクセスとシーケンシャルアクセスです。

ランダムアクセスが高速な媒体上のデータではクイックが有利
シーケンシャルアクセスがの方が速い、あるいはシーケンシャルアクセス
しか出来ない媒体ではマ―ジの方が有理です。

従って、全データをメモリにのせて処理して良いならクイック
HDDからデータを読みながら、メモリを余り使わずソートしたいならマージ

ということになります。

蛇足ですが、私ならソートはデータベースに任せます(SQLにorder by書くだけ)(^_^;)

No.3 回答者： kmee 回答日時： 2020/07/23 22:40

安定ソートの意味はご存知ですね?

では、なぜ「安定ソートの方がよい」と考えたのでしょうか?
「安定」という言葉の印象に引っぱられてないですか?


比較に使う値が等しかった場合、並び換え前の順位が残ることが保証されるのが「安全ソート」です。

例えば
　行番号 得点 名前
　--------
　1 90 田中
　....
　15 90 佐藤
　....
というデータを得点順にソートすることを考えます。

このとき、上記の 90点 が等しい値になります。
このとき、元の並び順が保存されて
　1 90 田中
　15 90 佐藤
となることが保証されているのが安定ソートです。


安定ソートとそうでないソートとで違いが出るのは「等しい値が複数あるとき」です。
全ての値が異なれば、どちらでも同じ結果になります。


どんなデータなのかをよく考えてみましょう。
○ 元のデータベースは整列済みなのですか?
　整列できてないデータを安定ソートで並び変えても「安定」である意味がありません。
○同じ「学籍番号」のデータが複数あるのですか?
　例えば「日付別出席記録」なら、日付と学籍番号の組になっていて、一つの学籍番号に複数の日付が対応しているでしょう
　「学生名簿」なら、重複しているのは変です。

No.2 回答者： satoumasaru 回答日時： 2020/07/23 22:14

No1です。

どちらかというと、おっしゃるとおり「安定ソート」であるマージソートでしょうね。
学生数ぐらいのデータでしたらそんなに速度差はでないでしょうし。

No.1 回答者： satoumasaru 回答日時： 2020/07/23 22:03

どちらでも良いです。

実務で使用する場合はライブラリを使用しますから。