List<T>のSort（）について

Question

こんにちは

初歩的な質問なのですが、教えてください。

List<int> myList = new List<int>();

myList.Add(100);

myList.Add(90);

     :

     :

myList.Sort();

を実行すると、必ず昇順ソートになるようですが、簡単に降順ソートにする方法はないのでしょうか?

１．myList.Sort()実行後、myList.Reverse()を実行する。

２．降順ソート用の関数を定義する。

３．(理解できていませんが）IComparerクラスなどを定義する。

など考えてみましたが、一発で降順ソートができる手立てはあるのでしょうか?

よろしくお願いします。

Answer 1

お使いの C# のバージョンによって、できることが違ってきますが、匿名デリゲートとかラムダ式を使うとシンプルに書けると思います。

配列やコレクション内の要素を並び替える: .NET Tips: C#, VB.NET, Visual Studio
http://dobon.net/vb/dotnet/programing/icomparer.html

Answer 2

.NET 3.5以降ですがLINQを使うという手もあります。

 

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var list = new List<int> { 3, 1, 5, 2, 6, 4 };
        var sorted = list.OrderBy(i => i).ToList();
        var sortedDesc = list.OrderByDescending(i => i).ToList();

        Console.WriteLine("-- ソート前");
        foreach (var i in list)
        {
            Console.Write(i + ", ");
        }
        Console.WriteLine();

        Console.WriteLine("-- OrderBy");
        foreach (var i in sorted)
        {
            Console.Write(i + ", ");
        }
        Console.WriteLine();

        Console.WriteLine("-- OrderByDescending");
        foreach (var i in sortedDesc)
        {
            Console.Write(i + ", ");
        }
        Console.WriteLine();
    }
}

 

実行すると、以下のような結果になります。

-- ソート前
3, 1, 5, 2, 6, 4,
-- OrderBy
1, 2, 3, 4, 5, 6,
-- OrderByDescending
6, 5, 4, 3, 2, 1,

---

かずき　Blog：http://d.hatena.ne.jp/okazuki/ VS 2010のデザイナでBlendのBehaviorをサポートするツール公開してます。 http://vsbehaviorsupport.codeplex.com/

Answer 3

以下が簡単かな？

 myList.Sort((x, y) => y.CompareTo(x));

 

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 4

totojo様
かずき_okazuki様
trapemiya様

ご回答ありがとうございます。
LINQに関しては、要素数が増えるとスピードダウンすると聞いたことがあるので、今回は除外しようと思います。
totojo様がご提示くださったサイトは見ていたのですが、IComparerクラスを勉強して対応してみようと思います。

ありがとうございました。

Answer 5

外池と申します。

List<T>のTには、何か、独自の型が入るんですよね？（思い込みが過ぎるかな・・・）　

だとすれば、ソートするには降順・昇順にかかわらず「大小関係」を定義してやらないといけないので、IComparableかIComparable<T>のインターフェイスの実装は必須なのではないかと・・・。LINQを使うにしても。

 

---

（ホームページを再開しました）

Answer 6

パフォーマンス重視なんですね。私が書いたラムダ式(Comparison)との比較に興味があったので比較してみました。

var list = new List<int>();

for (var i = 0; i < 10000000; i++)
    list.Add(i);

var st = new Stopwatch();
Console.WriteLine(Stopwatch.IsHighResolution);

st.Start();
list.Sort((x, y) => y.CompareTo(x));
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds.ToString());

list = new List<int>();

for (var i = 0; i < 10000000; i++)
    list.Add(i);

st = new Stopwatch();
IComparer<int> comp = new MyComparer();

st.Start();
list.Sort(comp);
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds.ToString());


public class MyComparer :System.Collections.Generic.IComparer<int>
{
    public int Compare(int x, int y)
    {
        return y.CompareTo(x);
    }
}

ラムダ式(Comparison)　　IComparer  　　差　　（単位 ms)  Windows 7 ultimate x64 Intel Core i7 930 2.80Ghz

4714                    4391           323
5278                    4929           349
5556                    4561           995
4714                    4392           322
5543                    4564           979
5237                    4910           327
5529                    4567           962
4943                    4287           656
5527                    4570           957
4713                    4397           316

 

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 7

そんなこと言ったら

list.Sort();
list.Reverse();

が断然速いですが…。 

Answer 8

外池です。念のため・・・、

Sortって、ドキュメントによれば、ＱｕｉｃｋＳｏｒｔとなっていますが・・・、

これ、最初から整列したものに対して適用すると、O(N^２）　（汗）

 

---

（ホームページを再開しました）

Answer 9

そんなこと言ったら

list.Sort();
list.Reverse();

が断然速いですが…。 

そうですね。Sort、Reverseもついでに計測してみました。また、ソートする前のListは、シャッフルするようにしました。

var list1 = new List<int>();
var list2 = new List<int>();
var list3 = new List<int>();

for (var i = 0; i < 10000000; i++)
    list1.Add(i);

list1 = list1.OrderBy(i => Guid.NewGuid()).ToList();    //シャッフル
list2 = list1.ToList();
list3 = list1.ToList();

var st = new Stopwatch();
Console.WriteLine(Stopwatch.IsHighResolution);

//１．ラムダ式(Comparison)でソート--------------------
st.Start();
list1.Sort((x, y) => y.CompareTo(x));
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds.ToString());

//２．IComparerでソート-------------------------------
st = new Stopwatch();
IComparer<int> comp = new MyComparer();

st.Start();
list2.Sort(comp);
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds.ToString());

//３．SortとReverseでソート---------------------------
st = new Stopwatch();

st.Start();
list3.Sort();
list3.Reverse();
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds.ToString());

 １．　　　　　　２．　　　　　　３．　　　単位 ms
7088        6391        1200
6985        6312        1201
7075        6601        1196
7636        7034        1196
6952        6528        1198

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 10

上の私の発言の追記です。コードを含む投稿を修正すると、コード間に空行がどんどん増えていくんで、修正しづらいんですよね・・・。この障害の報告してあったかな？

これ、最初から整列したものに対して適用すると、O(N^２）　（汗）

シャッフルするようにしました。シャッフルしなきゃと思っていたんですが、忘れていました。ご指摘ありがとうございます。

 

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 11

フフフフフッ、圧倒的じゃないか、引数なしSort()は

とか言いたくなりますね。

種明かしすると、引数なしだったり、Comperer<T>.Defaultを渡した場合は、ICompererを使わずネイティブコードで並べ替えが実行されます。

Answer 12

コードを含む投稿を修正すると、コード間に空行がどんどん増えていくんで、修正しづらいんですよね・・・。この障害の報告してあったかな？

とりあえず報告が無さそうだったので、報告しておきました。

コードブロックを含む投稿を開いて修正すると、コードブロックで１行毎に空行を挿入される。
http://social.msdn.microsoft.com/Forums/ja-JP/suggestja/thread/fb0eab28-6820-4530-9883-0a936d267086

 

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 13

種明かしすると、引数なしだったり、Comperer<T>.Defaultを渡した場合は、ICompererを使わずネイティブコードで並べ替えが実行されます。

なるほど。
外池さんも言われていますが、海外のどこかの掲示板でもQuick Sortと書かれていましたから、これがネイティブで実行されるということですね。
思った以上に大差でした。佐祐理さんの一言で計測してみて良かったです。勉強になりました。ありがとうございます。

 

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 14

外池さんも言われていますが、海外のどこかの掲示板でもQuick Sortと書かれていましたから、これがネイティブで実行されるということですね。

Quick Sortはアルゴリズム名で、List<T>.Sort()やArray.Sort()に明記されています。海外のどこかの掲示板を見なくても見つかるかと…。ネイティブ実行されることはstack overflowにもありますね。

Answer 15

外池です。私が「ドキュメント」と書いたのは、佐祐理さんが示しておられるページのことです。

IComparer<T>を渡した場合であっても、個々の要素の大小判定にはこれが使われるものの、全体の並べ替えのアルゴリズムはQuick Sortだと私は理解しています。

以下、独り言。

IComparer<T>の呼び出しに大きなペナルティーがあるんでしょうね。ネイティブ実行に比べて。当たり前か。

Quick Sortを選んだところ・・・、Microsoft殿らしいなあ、とも思います。私は、Heap Sortの方が好きです。Numerical Recipesの著者は、版を重ねる途中で宗旨替えしてますね。もともとHeap Sortが一押しだったようですが、今の版ではQuick Sortになっている。

---

（ホームページを再開しました）

Answer 16

IComparer<T>の呼び出しに大きなペナルティーがあるんでしょうね。ネイティブ実行に比べて。当たり前か。

.NET FrameworkにとってはIComperer<T>も入力引数なので、Compare()結果に矛盾がないか疑いながら並べ替える必要があったりする点もオーバーヘッドになるかも。

Quick Sortを選んだところ・・・、Microsoft殿らしいなあ、とも思います。私は、Heap Sortの方が好きです。Numerical Recipesの著者は、版を重ねる途中で宗旨替えしてますね。もともとHeap Sortが一押しだったようですが、今の版ではQuick Sortになっている。

libcにもqsort()があったりと、ライブラリで用意する場合はQuick Sortにせざるを得ないと思います。好きか嫌いかでいえば、私もHeap Sortが好きですが、同じO(n log n)であっても、Quick Sortの方が早いので。

# trapemiyaさんの「Quick Sortと書かれていましたから、これがネイティブで実行されるということですね」という言い回しが、Quick Sortをアルゴリズム以外の何かを指しているような表現に受取れたために念のため書きました。

Answer 17

# trapemiyaさんの「Quick Sortと書かれていましたから、これがネイティブで実行されるということですね」という言い回しが、Quick Sortをアルゴリズム以外の何かを指しているような表現に受取れたために念のため書きました。

アルゴリズムの意味で使っていました。というか、アルゴリズム名以外に私は知りません(^^;
とはいうものの、昔はソートを自分で書いたりしていましたが、最近は自分でソートを書くことは無くなってしまい、ソートアルゴリズムに関してはすっかり忘れてしまいました(^^;
私が関わる仕事の範囲では大量のデータを扱うシビアなソートを要求されることは無いですし、ソートはデータベースで行うことが多くなりましたし、パソコンの性能が上がったのも理由の一つでしょうか。
しかし、決してソートのアルゴリズムを勉強する必要は無いと言うつもりはありません。古い記事ですが、日経ソフトウエア 2000年1月号の　「ソートの書ける」プログラマになろう！　という記事を思い出しました。ソートもアルゴリズムですから、アルゴリズムを勉強することはプログラマとして幅が広がると思います。

 

---

★良い回答には回答済みマークを付けよう！ わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/

Answer 18

アルゴリズムでなくても。

例えば、このスレッドを起こしたmokosanさんは別スレッドでSortedListについて質問されています。List.Sort()は一括でソートしますが、SortedListは項目が増減されるたびにソートし直します。（と言っても毎回Quick Sortをするわけじゃないでしょうが。）
項目の増減が激しく、なおかつ常にソートされた状態が必要とされているのならSortedListが適しているでしょうが、そうではない場合、ソート状態を維持するコストが高くなるでしょう。
# 質問を読む限り、Dictionaryの方が適しているアクセス方法をしていますし…。 

とかとか、コストについては理解しておいた方がいいでしょうね。

Answer 19

LINQに関しては、要素数が増えるとスピードダウンすると聞いたことがあるので、今回は除外しようと思います。

私はLINQ星人ではないのでうまく説明できませんが、この記述に引っかかったので。

LINQには確かにオーバーヘッドはあります。それは事実なのですが、それに勝る利点があります。

まず前提として遅延実行されます。そのため要素数が増えても必要な要素にしかアクセスせずに済ます書き方ができます。その場合、要素数が増えてもスピードダウンしないでしょう。またAsParallel拡張メソッドなどもあり、簡単にマルチスレッド実行できる仕組みも用意されています。通常の書き方ならシングルスレッドで逐次的に処理するものもマルチスレッドで並列に処理することで高速化できたりもあります。

というわけで「LINQに関しては、要素数が増えるとスピードダウンする」とは「下手な人が試してみたところスピードダウンした」程度の意味ですので、ぜひぜひLINQも使ってみてください。