Help us understand the problem. What is going on with this article?

List.Sort((a,b)=>(a-b))について

More than 1 year has passed since last update.

はじめに

夏ぼっちカレンダー(仮)の18日目の記事です。
記事の中に間違いなどあれば指摘していただけると幸いです。

List.Sort((a,b)=>(a-b))がよく分からない

要素数5のリストの
List.Sort((a,b)=>(a-b))の中身を以下のコードで出力してみます。

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

class Program
{
    static void Main()
    {
        var list = new List<int>();
        for (int i=5; 1 <= i; --i)
        {
            list.Add(i);
        }

        Console.WriteLine("ソート前");
        Console.WriteLine();

        foreach (var i in list)
        {
            Console.Write($"{i} ");
        }
        Console.WriteLine();

        Console.WriteLine("ソート");
        Console.WriteLine();

        list.Sort((a, b) => {
            Console.Write($"a:{a} ");
            Console.Write($"b:{b} ");
            Console.WriteLine($"a-b:{a-b}");
            return a - b;
        });

        Console.WriteLine();
        Console.WriteLine("ソート後");
        Console.WriteLine();

        foreach (var l in list)
        {
            Console.Write($"{l} ");
        }
    }
}

すると以下のように出力されます

ソート前

5 4 3 2 1 

ソート

a:4 b:5 a-b:-1
a:3 b:5 a-b:-2
a:3 b:4 a-b:-1
a:2 b:5 a-b:-3
a:2 b:4 a-b:-2
a:2 b:3 a-b:-1
a:1 b:5 a-b:-4
a:1 b:4 a-b:-3
a:1 b:3 a-b:-2
a:1 b:2 a-b:-1

ソート後

1 2 3 4 5 

よく分からないところ

①それぞれのaとbの値の決め方
②ループの回る回数(処理の回数)
③returnされた値の利用方法

Sortについて

まず、順番が前後しますが「③returnされた値の利用方法」についてです。

Sortにはいくつか種類があり、
ここで使用されている種類は「Sort(Comparison)」です。
他に、Sort()やSort(IComparer)があります。

Sort(Comparison)はComparisonデリゲートから返された値が
負の場合に要素の位置を交換します。

つまり、
上の例では以下のことが起こっています。

① 5 4 3 2 1の配列が存在
② 4と5が比較され、-1が返される
③ 負の値が返されたので4と5の順番を逆にする
④ 4 5 3 2 1の配列になる
⑤ 3と5が比較され、-2が返される
⑥ 負の値が返されたので3と5の順番を逆にする
⑦ 4 3 5 2 1の配列になる

ここから、
「③returnされた値の利用方法」は
負の時に要素の順番を入れ替えることだということが分かります。

並び替えるアルゴリズムの選択

次に
「①それぞれのaとbの値の決め方」と「②ループの回る回数(処理の回数)」
についてです。

要素が16未満の際は「挿入ソート」
それ以外は(たぶん)イントロソート(クイックソート+ヒープソート)
の使用になるようです。

上の要素数は5だったので
挿入ソートが行われていました。

そのため、
「①それぞれのaとbの値の決め方」と「②ループの回る回数(処理の回数)」も
挿入ソートの方法に沿ったものになっていました。

要素数を20にするとクイックソートになりました。

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

class Program
{
    static void Main()
    {
        var list = new List<int>();
        for (int i = 20; 1 <= i; --i)
        {
            list.Add(i);
        }

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

        Console.WriteLine("ソート");
        Console.WriteLine();

        list.Sort((a, b) => {
            Console.Write($"a:{a} ");
            Console.Write($"b:{b} ");
            Console.WriteLine($"a-b:{a-b}");
            return a - b;
        });

        Console.WriteLine();
        Console.WriteLine("ソート後");
        Console.WriteLine();

        foreach (var l in list)
        {
            Console.Write($"{l} ");
        }
    }
}

以下のように出力されます

ソート前

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 

ソート

a:20 b:11 a-b:9
a:11 b:1 a-b:10
a:20 b:11 a-b:9
a:19 b:11 a-b:8
a:11 b:3 a-b:8
a:18 b:11 a-b:7
a:11 b:4 a-b:7
a:17 b:11 a-b:6
a:11 b:5 a-b:6
a:16 b:11 a-b:5
a:11 b:6 a-b:5
a:15 b:11 a-b:4
a:11 b:7 a-b:4
a:14 b:11 a-b:3
a:11 b:8 a-b:3
a:13 b:11 a-b:2
a:11 b:9 a-b:2
a:12 b:11 a-b:1
a:11 b:10 a-b:1
a:2 b:11 a-b:-9
a:12 b:11 a-b:1
a:11 b:2 a-b:9
a:14 b:13 a-b:1
a:15 b:14 a-b:1
a:16 b:15 a-b:1
a:17 b:16 a-b:1
a:18 b:17 a-b:1
a:19 b:18 a-b:1
a:12 b:19 a-b:-7
a:12 b:18 a-b:-6
a:12 b:17 a-b:-5
a:12 b:16 a-b:-4
a:12 b:15 a-b:-3
a:12 b:14 a-b:-2
a:12 b:13 a-b:-1
a:20 b:19 a-b:1
a:3 b:1 a-b:2
a:4 b:3 a-b:1
a:5 b:4 a-b:1
a:6 b:5 a-b:1
a:7 b:6 a-b:1
a:8 b:7 a-b:1
a:9 b:8 a-b:1
a:10 b:9 a-b:1
a:2 b:10 a-b:-8
a:2 b:9 a-b:-7
a:2 b:8 a-b:-6
a:2 b:7 a-b:-5
a:2 b:6 a-b:-4
a:2 b:5 a-b:-3
a:2 b:4 a-b:-2
a:2 b:3 a-b:-1
a:2 b:1 a-b:1

ソート後

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

ここから、
「①それぞれのaとbの値の決め方」と「②ループの回る回数」は、
ソートする際に使用するアルゴリズムによることが分かりました。

まとめ

・Sort(Comparison)はComparisonデリゲートから返された値が、負の場合に要素の位置を交換する
・デリゲートの引数の値の決め方と、処理の回数はアルゴリズムによる

参考

C#の配列やListをソートする (List.Sort)
List.Sort Method
C#の安定ソートを検討
ノームソート
【Unity】ソートアルゴリズム12種を可視化してみた
Sortメソッドの並び替え順序
ヒープソート
イントロソート
挿入ソート
C# デリゲートについて
Comparison Delegate

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away