Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@nabemax

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

Posted at

はじめに

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

プロローグ

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

クライアント「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なりで軽く実装しておくのが楽だし、管理しやすいと思います。

1
2
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?