【C#】ソートの実装方法あれこれ

はじめに

前回の記事を書きながら、ソートの実装方法って色んなバリエーションあるなと思ったので、ストーリー仕立てにしてまとめてみました。

プロローグ

とあるオフィスで、とあるクライアントから下記プログラムの修正依頼がきました。

クライアント「Listのソート処理を実装してくれ。ただ各所で信じられないほど複雑な処理を行っているので、弄ってよいのはSortメソッド内と話の都合上Personクラスだけとしてください。ソートのキーは・・・とりあえずIDで良いです。」

Program.cs

using System;
using System.Collections.Generic;

class Program {

  static void Main(string[] args) {
    List<Person> persons = new List<Person>();
    SuperFukuzatsuShori(persons);
    HighperFukuzatsuShori(persons);
    Sort(persons);
    PrintPersons(persons);
    Console.ReadLine();
  }

  static void SuperFukuzatsuShori(List<Person> persons) {
    persons.Add(new Person(6, "Watanabe", "F", 30));
    persons.Add(new Person(7, "Yamamoto", "M", 30));
    persons.Add(new Person(8, "Nakamura", "F", 30));
    persons.Add(new Person(9, "Kobayashi", "M", 30));
    persons.Add(new Person(10, "Katou", "F", 30));
  }

  static void HighperFukuzatsuShori(List<Person> persons) {
    persons.Add(new Person(1, "Yamada", "M", 25));
    persons.Add(new Person(2, "Suzuki", "F", 25));
    persons.Add(new Person(3, "Takahashi", "M", 25));
    persons.Add(new Person(4, "Tanaka", "F", 25));
    persons.Add(new Person(5, "Itou", "M", 25));
  }

  static void PrintPersons(List<Person> persons) {
    Console.WriteLine("| # | ID | Name      | Sex | Age |");
    Console.WriteLine("+---+----+-----------+-----+-----+");
    for (int i = 0; i < persons.Count; i++) {
      Person person = persons[i];
      Console.WriteLine($"|{i + 1,2} | {person.Id,2} | {person.Name,-9} |  {person.Sex,1}  |  {person.Age,2} |");
    }
  }

  // 弄ってOK！
  static void Sort(List<Person> persons) {
    // TODO: Listをソートする
  }

}

Person.cs

// 弄ってOK！
class Person {

  public Person(int id, string name, string sex, int age) {
    this.Id = id;
    this.Name = name;
    this.Sex = sex;
    this.Age = age;
  }

  public int Id { get; private set; }
  public string Name { get; private set; }
  public string Sex { get; private set; }
  public int Age { get; set; }
}

新人A君の場合

新人A君は繰り返し、条件分岐といった基本的なプログラムを覚えてばかりです。必死に悩んだ結果、力業で解決することにしました。

  static void Sort(List<Person> persons) {
    // IDが大きい要素を末尾に寄せていく
    for (int i = 0; i < 9; i++) {
      for (int j = i + 1; j < 10; j++) {
        // 隣のIDが大きい場合は場所を入れ替える
        if (persons[i].Id > persons[j].Id) {
          Person tmp = persons[j];
          persons[j] = persons[i];
          persons[i] = tmp;
        }
      }
    }
  }

• 通称バブルソート
• クイックソート等より効率的なアルゴリズムにするべき
  • そもそも自力でソートアルゴリズムまで実装する必要もないが
• プログラム経験ゼロの人が自力でこれ実装してきたらヤバイ

社会人1年目B君の場合

B君は1年間の仕事を経て、言語仕様に多少詳しくなりました。そこで最近勉強したList#Sort()とIComparerを使いソート処理を実装することにしました。

Program.cs

  static void Sort(List<Person> persons) {
    persons.Sort();
  }

Person.cs

class Person : System.IComparable<Person> { // IComparable<T> を継承し
  // 中略
  public int CompareTo(Person person) { // CompareTo を実装
    return Id - person.Id; // ID の大小で比較
  }
}

• 基本形
• 既存機能をしっかり使えていてGOOD

社会人2年目C君

社会の荒波に揉まれたC君はクライアントの話しを聞いて察しました。

C君「あの歯切れの悪さ・・・Name辺りもソートに使うようになるぞ・・・！」

そこで先を見越し、IComparerで汎用性をもった実装することにしました。

Program.cs

  static void Sort(List<Person> persons) {
    persons.Sort(new PersonComparerId()); // Comparer で比較
    // persons.Sort(new PersonComparerName()); // Name でのソートも出来る
  }

Comparers.cs

using System.Collections.Generic;

class PersonComparerId : IComparer<Person> { // IComparer を継承し
  public int Compare(Person x, Person y) { // Comparer を実装し
    return x.Id - y.Id; // ID を比較
  }
}

// どうせなので Name を比較する Comparer も作った
class PersonComparerName : IComparer<Person> {
  public int Compare(Person x, Person y) {
    return x.Name.CompareTo(y.Name);
  }
}

• 汎用性があってGOOD
• コード量の増加が少し気になる・・・
• 実際のところ、Name の比較まで勝手に実装したら怒られると思うけどご愛敬

社会人2年目D君

D君はC君の同期でスマートな事が大好きです。コードを短くスマートに書く事が大正義だと思っています。少しSortについて調べたところ、Comparisonを用いたクールなソートを発見したので実装することにしました。

Program.cs

  static void Sort(List<Person> persons) {
    persons.Sort((Comparison<Person>)((x, y) => x.Id - y.Id)); // ラムダも使って一行！
  }

• 超クール
• コード修正量激小
• ID や Name に対する Comparison を定数として実装すればそれなりに汎用性もある

社会人3年目Eさん

クライアントと長い付き合いのEさんは察しました。

Eさん「あの歯切れの悪さ・・・Name はおろか降順も実装する必要が出てきそうだ・・・！」

そこでC君のコードにひと手間加えて、昇順、降順も選択できるように実装しました。

Program.cs

  static void Sort(List<Person> persons) {
    persons.Sort(new PersonComparerId(false)); // ID昇順
    // persons.Sort(new PersonComparerId(true)); // ID降順
  }

Comparers.cs

using System.Collections.Generic;

class PersonComparerId : IComparer<Person> {

  private bool _desc; // 降順フラグ

  public PersonComparerId(bool desc = false) { // コンストラクタを追加
    _desc = desc; // 降順フラグを受け取る
  }

  public int Compare(Person x, Person y) {
    if (_desc) {
      return y.Id - x.Id; // 降順の場合は前後要素を入れ替えて比較する
    } else {
      return x.Id - y.Id; // 昇順の場合は今まで通り比較する
    }
  }
}

• IComparer の可能性を実感
• 一方でコード修正量の多さも流石に気になり始める

社会人X年目Fさん

最近デザインパターンを勉強したFさん（というか僕）は思いました。

Fさん「勉強したデザインパターンをどうしても使いたいので各要素を組み合わせてソートできるようにしよう。」

今までの実装を振り返ると、検索機能に新しい検索機能を追加しているように思えます。ということは、デコレータパターンを使えそうです。

Program.cs

  static void Sort(List<Person> persons) {
    persons.Sort(new PersonComparerId()); // ID昇順
    // persons.Sort(new PersonComparerDesc(new PersonComparerId())); // ID降順
    // persons.Sort(new PersonComparerSex(new PersonComparerName())); // 性別→名前昇順
    // persons.Sort(new PersonComparerDesc(new PersonComparerSex(new PersonComparerName()))); // 性別→名前降順
  }

Comparers.cs

using System.Collections.Generic;

abstract class PersonComparer : Comparer<Person> { } // Component

class PersonComparerId : PersonComparer { // ConcreteComponent

  public override int Compare(Person x, Person y) { // ID で比較
    return x.Id - y.Id;
  }

}

abstract class PersonComparerDecorator : PersonComparer { // Decorator

  protected Comparer<Person> _comparer;

  public PersonComparerDecorator(Comparer<Person> comparer) {
    _comparer = comparer ?? new PersonComparerId();
  }

}

class PersonComparerDesc : PersonComparerDecorator { // ConcreteDecorator

  public PersonComparerDesc(Comparer<Person> comparer) : base(comparer) { }

  public override int Compare(Person x, Person y) { // 要素を入れ替えて結果を降順にする
    return _comparer.Compare(y, x);
  }

}

class PersonComparerName : PersonComparerDecorator { // ConcreteDecorator

  public PersonComparerName(Comparer<Person> comparer = null) : base(comparer) { }

  public override int Compare(Person x, Person y) { // Name で比較
    int result = x.Name.CompareTo(y.Name);
    if (result == 0) {
      result = _comparer.Compare(x, y); // 同じ名前の場合は別のキーで比較
    }
    return result;
  }

}

// 省略

• 各要素を組み合わせてソート可能で汎用性高そう
• 引き換えにコード量が爆増＆分かりづらい
• YAGNI原則に喧嘩を売るスタイル
• Descを複数回使うと・・・

まとめ

最近はフィルター処理やソート処理をデコレータを使って実装し、無限の可能性を感じています。ただ前述の通りコード量が増えがちですし、処理が理解がし辛いデメリットもあるので、プロジェクトで使うことはないだろうなと・・・。実際のところ、C、D君のようにIComparerなりComparisonなりで軽く実装しておくのが楽だし、管理しやすいと思います。