質問: ``` A,10,50,32 B,30,60,21 C,15,45,61 ``` というcsvファイルを読み込んで、A~Cの順番を崩さずに次の条件を満たしたdat、csvファイルを出力したいです。順番を崩したくない理由は、A, B, Cの並び順によって一意な値(配列の添え字)を割り振るためです。 * 降順にソートした結果の4列目のデータだけのdatファイル 期待する出力: ``` 61 32 21 ``` * 5列目に4列目のデータで降順ソートした時のランキング順位 期待する出力: ``` A,10,50,32,2 B,30,60,21,3 C,15,45,61,1 ``` またソートには平均計算時間が早いクイックソートを使いたいです。 --- 現在はどうやって実装するかを考えている段階で、配列に3列目だけを代入してクイックソートを実施して、順位付けは別でfor文などを使って実現しようと考えていました。 しかしせっかくクイックソートで順位とほぼ等しい降順データが取れているのに順位付けのために別途繰り返し構文を書くことが非効率に思えてしまい、何か方法がないかと悩んでいます。 クイックソートとランキング順位付けを同時に実行することは可能ですか?あるいはソートアルゴリズムを変更すれば可能でしょうか? 以上の点についてご教授よろしくお願いします。
回答: > > 順位付けのために別途繰り返し構文を書くことが非効率に思えてしまい、 > > > 順位付けを別処理にすることは非効率とは思えません。 クイックソートの平均計算量は O(n log n)、最悪で O(n^2) ですが、その後の順位付けは O(n) で済みます。 また、ソート中に順位を確定するのは難しいです。実装したとしても順位確定判定用のIF文を毎回通すことになり、かえって非効率になってしまうと思います。効率を求めるのであれば、繰り返しの回数よりも条件分岐の回数に注意したほうがよいと思います。 どうしてもソートと順位付けを同じ処理で行いたい場合はバブルソートであれば簡単に実装すればできそうですが、確実に遅くなるのでやはりおすすめしません。 さらに、複数の機能を1つの処理にしてしまうというのはおすすめできません。メンテナンスのしやすさを考えると機能単位で処理がまとまっていたほうがわかりやすいかと思います。 参考として、私がC#で実装するとしたら以下のようなコードになります。4列目の値をキーにリストそのものをソートして新しいリストを作成しています。 ``` public class Data { public string Name {get; set;} public int Value1 {get; set;} public int Value2 {get; set;} public int Value3 {get; set;} public int Rank {get; set;} // 入力CVSを読み込んだ時点ではRankは未定 } public void Sample(List source) { // Value3でソートしたリストを作る。 // sourceとrankingは並び順が異なるだけで、要素のデータは同じものを参照している List ranking = source.OrderByDescending(e => e.Value3).ToList(); // 順位付け。Value3が同値だった場合の対応は未実装です int rank = 1; foreach(var data in ranking) { data.Rank = rank; rank++; } // 出力:Value3 foreach(var data in ranking) { Console.WriteLine($"{data.Value3}"); } // 出力:ランクを付加したデータ foreach(var data in source) { Console.WriteLine($"{data.Name},{data.Value1},{data.Value2},{data.Value3},{data.Rank}"); } } ```