ここでは、.NET Frameworkに用意されているArray.SortやEnumerable.OrderByなどのソート処理を使わずに、独自にジェネリックなソートアルゴリズムを実装する方法について見ていきます。 以下で紹介するコードはそのまま実用することもできますが、ソート処理の内部動作とジェネリックインターフェイス・ジェネリックデリゲートの関わり、ジェネリックメソッドの実装について理解することを主な目的としています。
導入
ジェネリックなソートアルゴリズムを実装するにあたり、基本形としてint/Integer型の配列をソートして昇順に並べ替えるコードを考えます。 ここでは、実装するソートアルゴリズムとしてクイックソートを使用することにします。
クイックソートでint型の配列をソートするコード
using System;
class Sample {
static void Main()
{
int[] data = {3, 5, 4, 2, 6, 1};
QSort(data, 0, data.Length - 1);
foreach (int d in data) {
Console.Write("{0}, ", d);
}
Console.WriteLine();
}
// クイックソート
static void QSort(int[] data, int left, int right)
{
if (right <= left)
return;
int pivot = data[(left + right) / 2]; // ピボットの選択
int i = left;
int j = right;
for (;;) {
while (data[i] < pivot)
i++;
while (pivot < data[j])
j--;
if (j <= i)
break;
// 入れ替え
int temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
j--;
}
QSort(data, left, i - 1);
QSort(data, j + 1, right);
}
}
クイックソートでint型の配列をソートするコード
Imports System
Class Sample
Shared Sub Main()
Dim data() As Integer = New Integer() {3, 5, 4, 2, 6, 1}
QSort(data, 0, data.Length - 1)
For Each d As Integer In data
Console.Write("{0}, ", d)
Next
Console.WriteLine()
End Sub
' クイックソート
Shared Sub QSort(ByVal data() As Integer, ByVal left As Integer, ByVal right As Integer)
If right <= left Then Exit Sub
Dim pivot As Integer = data((left + right) \ 2) ' ピボットの選択
Dim i As Integer = left
Dim j As Integer = right
Do
While data(i) < pivot
i += 1
End While
While pivot < data(j)
j -= 1
End While
If j <= i Then Exit Do
' 入れ替え
Dim temp As Integer = data(i)
data(i) = data(j)
data(j) = temp
i += 1
j -= 1
Loop
QSort(data, left, i - 1)
QSort(data, j + 1, right)
End Sub
End Class
実行結果
1, 2, 3, 4, 5, 6,
このコードを書き換えて、double型の配列をソートできるようにすると次のようになります。
クイックソートでdouble型の配列をソートするコード
using System;
class Sample {
static void Main()
{
double[] data = {0.3, 0.5, 0.4, 0.2, 0.6, 0.1};
QSort(data, 0, data.Length - 1);
foreach (double d in data) {
Console.Write("{0}, ", d);
}
Console.WriteLine();
}
// クイックソート
static void QSort(double[] data, int left, int right)
{
if (right <= left)
return;
double pivot = data[(left + right) / 2]; // ピボットの選択
int i = left;
int j = right;
for (;;) {
while (data[i] < pivot)
i++;
while (pivot < data[j])
j--;
if (j <= i)
break;
// 入れ替え
double temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
j--;
}
QSort(data, left, i - 1);
QSort(data, j + 1, right);
}
}
クイックソートでdouble型の配列をソートするコード
Imports System
Class Sample
Shared Sub Main()
Dim data() As Double = New Double() {0.3, 0.5, 0.4, 0.2, 0.6, 0.1}
QSort(data, 0, data.Length - 1)
For Each d As Double In data
Console.Write("{0}, ", d)
Next
Console.WriteLine()
End Sub
' クイックソート
Shared Sub QSort(ByVal data() As Double, ByVal left As Integer, ByVal right As Integer)
If right <= left Then Exit Sub
Dim pivot As Double = data((left + right) \ 2) ' ピボットの選択
Dim i As Integer = left
Dim j As Integer = right
Do
While data(i) < pivot
i += 1
End While
While pivot < data(j)
j -= 1
End While
If j <= i Then Exit Do
' 入れ替え
Dim temp As Double = data(i)
data(i) = data(j)
data(j) = temp
i += 1
j -= 1
Loop
QSort(data, left, i - 1)
QSort(data, j + 1, right)
End Sub
End Class
実行結果
0.1, 0.2, 0.3, 0.4, 0.5, 0.6,
このように、扱うデータの型が変わっているだけで、それ以外のコード(ソートのアルゴリズム部分)は全く同ものを流用することができます。 そこで、このソート処理をどのような型に対しても適用できるよう、このQSortメソッドをジェネリックメソッド化することを考えます。
ジェネリックメソッド化
先のコードでソート対象のデータ型として使用していたdoubleの個所を、ジェネリック型Tに置き換えることでジェネリックメソッド化することを目指します。
データ型をパラメータ化したジェネリックなクイックソート
using System;
class Sample {
static void Main()
{
double[] data = {0.3, 0.5, 0.4, 0.2, 0.6, 0.1};
QSort<double>(data, 0, data.Length - 1);
foreach (double d in data) {
Console.Write("{0}, ", d);
}
Console.WriteLine();
}
// ジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right)
{
if (right <= left)
return;
T pivot = data[(left + right) / 2];
int i = left;
int j = right;
for (;;) {
while (data[i] < pivot) // error CS0019: 演算子 '<' を 'T' と 'T' 型のオペランドに適用することはできません。
i++;
while (pivot < data[j]) // error CS0019: 演算子 '<' を 'T' と 'T' 型のオペランドに適用することはできません。
j--;
if (j <= i)
break;
T temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
j--;
}
QSort(data, left, i - 1);
QSort(data, j + 1, right);
}
}
データ型をパラメータ化したジェネリックなクイックソート
Imports System
Class Sample
Shared Sub Main()
Dim data() As Double = New Double() {0.3, 0.5, 0.4, 0.2, 0.6, 0.1}
QSort(Of Double)(data, 0, data.Length - 1)
For Each d As Double In data
Console.Write("{0}, ", d)
Next
Console.WriteLine()
End Sub
' ジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer)
If right <= left Then Exit Sub
Dim pivot As T = data((left + right) \ 2)
Dim i As Integer = left
Dim j As Integer = right
Do
While data(i) < pivot ' error BC30452: 演算子 '<' は、型 'T' および 'T' に対して定義されていません。
i += 1
End While
While pivot < data(j) ' error BC30452: 演算子 '<' は、型 'T' および 'T' に対して定義されていません。
j -= 1
End While
If j <= i Then Exit Do
Dim temp As T = data(i)
data(i) = data(j)
data(j) = temp
i += 1
j -= 1
Loop
QSort(data, left, i - 1)
QSort(data, j + 1, right)
End Sub
End Class
しかし単純に型をジェネリック型パラメータTに置き換えるだけでは上記のようにコンパイルエラーとなります。
intやdoubleでは比較演算子<が使用できるので、これによって値の大小関係を比較することができます。 一方ジェネリック型パラメータのTは、intやdoubleとなる場合があるだけでなく、比較演算子を持たない型となる場合もあります。 つまり、型Tは必ずしも比較演算子による大小関係の比較は行えないことから、上記のようなコンパイルエラーが発生します。
そのため、ジェネリック型同士を比較するには比較演算子ではなく他の方法によって比較する必要があります。 このような目的にはIComparer<T>インターフェイスを使うことができます。 IComparer<T>インターフェイスのCompareメソッドは引数に指定した二つの値の大小関係に応じた戻り値を返すので、これを比較演算子の代わりに使うことができます。 Array.Sortメソッドなども、IComparer<T>インターフェイスを指定することにより比較演算子を持たない型のソートができるようになっています。
IComparer<T>による大小比較のパラメータ化
比較演算子の代わりとして使用するIComparer<T>を指定できるようQSortメソッドの引数を増やし、大小関係の比較をIComparer<T>.Compareメソッドで行うように書き換えると次のようになります。
IComparer<T>.Compareで値を比較するようにしたジェネリックなクイックソート
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
double[] data = {0.3, 0.5, 0.4, 0.2, 0.6, 0.1};
QSort<double>(data, 0, data.Length - 1, Comparer<double>.Default); // デフォルトの比較子を指定
foreach (double d in data) {
Console.Write("{0}, ", d);
}
Console.WriteLine();
}
// ジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right, IComparer<T> comparer)
{
if (right <= left)
return;
T pivot = data[(left + right) / 2];
int i = left;
int j = right;
for (;;) {
// IComparer<T>を使って大小関係を比較する
while (comparer.Compare(data[i], pivot) < 0)
i++;
while (comparer.Compare(pivot, data[j]) < 0)
j--;
if (j <= i)
break;
T temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
j--;
}
QSort(data, left, i - 1, comparer);
QSort(data, j + 1, right, comparer);
}
}
IComparer<T>.Compareで値を比較するようにしたジェネリックなクイックソート
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
Dim data() As Double = New Double() {0.3, 0.5, 0.4, 0.2, 0.6, 0.1}
QSort(Of Double)(data, 0, data.Length - 1, Comparer(Of Double).Default)
For Each d As Double In data
Console.Write("{0}, ", d)
Next
Console.WriteLine()
End Sub
' ジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer, ByVal comparer As IComparer(Of T))
If right <= left Then Exit Sub
Dim pivot As T = data((left + right) \ 2)
Dim i As Integer = left
Dim j As Integer = right
Do
' IComparer(Of T)を使って大小関係を比較する
While comparer.Compare(data(i), pivot) < 0
i += 1
End While
While comparer.Compare(pivot, data(j)) < 0
j -= 1
End While
If j <= i Then Exit Do
Dim temp As T = data(i)
data(i) = data(j)
data(j) = temp
i += 1
j -= 1
Loop
QSort(data, left, i - 1, comparer)
QSort(data, j + 1, right, comparer)
End Sub
End Class
実行結果
0.1, 0.2, 0.3, 0.4, 0.5, 0.6,
これにより、どのような型でもソートできるジェネリックなメソッドを作成することができました。 またソート順序をIComparer<T>によって定義・指定できるようになるため、デフォルトとは異なる順序でソートしたい場合、例えば文字列をソートする際に大文字小文字の違いを無視する目的でStringComparer.OrdinalIgnoreCaseを指定する、といった使い方ができるようになります。
利便性の向上
基本型のIComparer<T>の省略
ここまでの実装では、比較演算子を持つintやdoubleなどの基本型の場合でも必ずIComparer<T>を指定する必要があります。 基本型の比較を行うIComparer<T>はComparer<T>.Defaultプロパティを参照するだけで取得できますが、それでもこれを毎回指定するのは不便です。
そこで、次のようにIComparer<T>を指定しないオーバーロードを増やすことにより、引数の数をジェネリック化する前と同じ数にすることができます。
IComparer<T>の指定を省略できるようにしたジェネリックなクイックソート
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// double型配列のクイックソート
double[] dataDouble = {0.3, 0.5, 0.4, 0.2, 0.6, 0.1};
QSort(dataDouble, 0, dataDouble.Length - 1);
foreach (double d in dataDouble) {
Console.Write("{0}, ", d);
}
Console.WriteLine();
// 文字列型配列のクイックソート
string[] dataString = {"a", "A", "C", "b", "abc", "B", "c"};
// 大文字小文字の違いを無視して比較するIComparer<T>を指定してソート
QSort(dataString, 0, dataString.Length - 1, StringComparer.OrdinalIgnoreCase);
foreach (string s in dataString) {
Console.Write("{0}, ", s);
}
Console.WriteLine();
}
// IComparer<T>を指定しないバージョンのジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right)
{
QSort(data, left, right, Comparer<T>.Default); // デフォルトの比較子を指定
}
// IComparer<T>を引数にとるバージョンのジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right, IComparer<T> comparer)
{
if (right <= left)
return;
T pivot = data[(left + right) / 2];
int i = left;
int j = right;
for (;;) {
// IComparer<T>を使って二つの値の大小関係を比較する
while (comparer.Compare(data[i], pivot) < 0)
i++;
while (comparer.Compare(pivot, data[j]) < 0)
j--;
if (j <= i)
break;
T temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
j--;
}
QSort(data, left, i - 1, comparer);
QSort(data, j + 1, right, comparer);
}
}
IComparer<T>の指定を省略できるようにしたジェネリックなクイックソート
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' Double型配列のクイックソート
Dim dataDouble() As Double = New Double() {0.3, 0.5, 0.4, 0.2, 0.6, 0.1}
QSort(dataDouble, 0, dataDouble.Length - 1)
For Each d As Double In dataDouble
Console.Write("{0}, ", d)
Next
Console.WriteLine()
' 文字列型配列のクイックソート
Dim dataString() As String = New String() {"a", "A", "C", "b", "abc", "B", "c"}
' 大文字小文字の違いを無視して比較するIComparer<T>を指定してソート
QSort(dataString, 0, dataString.Length - 1, StringComparer.OrdinalIgnoreCase)
For Each s As String In dataString
Console.Write("{0}, ", s)
Next
Console.WriteLine()
End Sub
' IComparer(Of T)を指定しないバージョンのジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer)
QSort(data, left, right, Comparer(Of T).Default) ' デフォルトの比較子を指定
End Sub
' IComparer(Of T)を引数にとるバージョンのジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer, ByVal comparer As IComparer(Of T))
If right <= left Then Exit Sub
Dim pivot As T = data((left + right) \ 2)
Dim i As Integer = left
Dim j As Integer = right
Do
' IComparer(Of T)を使って二つの値の大小関係を比較する
While comparer.Compare(data(i), pivot) < 0
i += 1
End While
While comparer.Compare(pivot, data(j)) < 0
j -= 1
End While
If j <= i Then Exit Do
Dim temp As T = data(i)
data(i) = data(j)
data(j) = temp
i += 1
j -= 1
Loop
QSort(data, left, i - 1, comparer)
QSort(data, j + 1, right, comparer)
End Sub
End Class
実行結果
0.1, 0.2, 0.3, 0.4, 0.5, 0.6, A, a, abc, B, b, c, C,
Comparison<T>の導入
ソート順序の定義にIComparer<T>を使用する場合、IComparer<T>を実装したクラスを用意する必要があります。 一方、Comparison<T>デリゲートを使えば、単にソート順序を定義したメソッドやラムダ式を用意するだけでよくなるため、わざわざクラスを用意する必要がなくなり、実装を簡略化できます。
従って、IComparer<T>.Comparerメソッドと同じようにComparison<T>を使うオーバーロードも増やせば、より使いやすくすることができます。
Comparison<T>を指定できるようにしたジェネリックなクイックソート
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
string[] data = {"a", "Aa", "ABC", "bbbb", "abc", "B", "cc"};
// 大文字小文字の違いを無視して比較するIComparer<T>を指定してソート
QSort(data, 0, data.Length - 1, StringComparer.OrdinalIgnoreCase);
foreach (string s in data) {
Console.Write("{0}, ", s);
}
Console.WriteLine();
// 文字列同士の長さを比較するラムダ式を指定してソート
QSort(data, 0, data.Length - 1, (x, y) => x.Length - y.Length);
foreach (string s in data) {
Console.Write("{0}, ", s);
}
Console.WriteLine();
}
// IComparer<T>を指定しないバージョンのジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right)
{
QSort(data, left, right, Comparer<T>.Default); // デフォルトの比較子を指定
}
// IComparer<T>を引数にとるバージョンのジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right, IComparer<T> comparer)
{
// IComparer<T>.CompareメソッドをComparison<T>デリゲートに変換して渡す
QSort(data, left, right, comparer.Compare);
}
// Comparison<T>を引数にとるバージョンのジェネリックなクイックソート
static void QSort<T>(T[] data, int left, int right, Comparison<T> compare)
{
if (right <= left)
return;
T pivot = data[(left + right) / 2];
int i = left;
int j = right;
for (;;) {
// Comparison<T>を使って二つの値の大小関係を比較する
while (compare(data[i], pivot) < 0)
i++;
while (compare(pivot, data[j]) < 0)
j--;
if (j <= i)
break;
T temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
j--;
}
QSort(data, left, i - 1, compare);
QSort(data, j + 1, right, compare);
}
}
Comparison<T>を指定できるようにしたジェネリックなクイックソート
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
Dim data() As String = New String() {"a", "Aa", "ABC", "bbbb", "abc", "B", "cc"}
' 大文字小文字の違いを無視して比較するIComparer<T>を指定してソート
QSort(data, 0, data.Length - 1, StringComparer.OrdinalIgnoreCase)
For Each s As String In data
Console.Write("{0}, ", s)
Next
Console.WriteLine()
' 文字列同士の長さを比較するラムダ式を指定してソート
QSort(data, 0, data.Length - 1, Function(x, y) x.Length - y.Length)
For Each s As String In data
Console.Write("{0}, ", s)
Next
Console.WriteLine()
End Sub
' IComparer(Of T)を指定しないバージョンのジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer)
QSort(data, left, right, Comparer(Of T).Default) ' デフォルトの比較子を指定
End Sub
' IComparer(Of T)を引数にとるバージョンのジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer, ByVal comparer As IComparer(Of T))
' IComparer(Of T).CompareメソッドをComparison(Of T)デリゲートに変換して渡す
QSort(data, left, right, AddressOf comparer.Compare)
End Sub
' Comparison(Of T)を引数にとるバージョンのジェネリックなクイックソート
Shared Sub QSort(Of T)(ByVal data() As T, ByVal left As Integer, ByVal right As Integer, ByVal compare As Comparison(Of T))
If right <= left Then Exit Sub
Dim pivot As T = data((left + right) \ 2)
Dim i As Integer = left
Dim j As Integer = right
Do
' Comparison(Of T)を使って二つの値の大小関係を比較する
While compare(data(i), pivot) < 0
i += 1
End While
While compare(pivot, data(j)) < 0
j -= 1
End While
If j <= i Then Exit Do
Dim temp As T = data(i)
data(i) = data(j)
data(j) = temp
i += 1
j -= 1
Loop
QSort(data, left, i - 1, compare)
QSort(data, j + 1, right, compare)
End Sub
End Class
実行結果
a, Aa, abc, ABC, B, bbbb, cc, B, a, cc, Aa, abc, ABC, bbbb,
発展
ここではソートアルゴリズムにクイックソートを使用しましたが、それ以外のソートアルゴリズムの場合もここでの手順と同様にして実装することができます。
ここまでで紹介したコードではComparer<T>.DefaultやStringComparerなどのすでに用意されているIComparer<T>を使用しましたが、IComparer<T>を適切に実装することにより、基本型だけでなく独自に作成したクラスや構造体など任意の型のソート順や、複数キーによるソートも定義できるようになります。
IComparer<T>の実装方法などについては大小関係の定義と比較や複合型のソート・複数キーでのソートを参照してください。
ここではソート対象を配列(T[])としましたが、これをIList<T>にすれば、配列だけでなくList<T>を含む幅広いコレクション型のソートに対応できるようになります。