2013-12-09T23:01:23の更新内容

programming/netfx/sorting/9_generic_sort_algorithm/index.wiki.txt

current previous
1,777 0,0
+
${smdncms:title,ジェネリックなソートアルゴリズムの実装}
+
${smdncms:keywords,ソート,アルゴリズム}
+
${smdncms:document_versions,codelang=cs,codelang=vb}
+

          
+
#navi(..)
+

          
+
ここでは、.NET Frameworkに用意されている[[Array.SortやEnumerable.OrderBy>programming/netfx/sorting/0_basictypes]]などのソート処理を使わずに、独自にジェネリックなソートアルゴリズムを実装する方法について見ていきます。 以下で紹介するコードはそのまま実用することもできますが、ソート処理の内部動作とジェネリックインターフェイス・ジェネリックデリゲートの関わり、ジェネリックメソッドの実装について理解することを主な目的としています。
+

          
+
-関連するページ
+
--[[programming/tips/sort_algorithms]]
+
--[[programming/netfx/comparison/0_comparison]]
+
--[[programming/netfx/string/2_2_compareoptions]]
+
--[[programming/netfx/delegate/0_abstract]]
+
--[[programming/vb.net/generics]] (VB)
+

          
+
#googleadunit(banner)
+

          
+
ジェネリックなソートアルゴリズムを実装するにあたり、基本形としてint/Integer型の配列をソートして昇順に並べ替えるコードを考えます。 ここでは、実装するソートアルゴリズムとしてクイックソートを使用することにします。
+

          
+
#tabpage(codelang=cs,container-title=クイックソートでint型の配列をソートするコード)
+
#code{{
+
using System;
+

          
+
public class Sample {
+
  public 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);
+
  }
+
}
+
}}
+
#tabpage(codelang=vb)
+
#code{{
+
Imports System
+

          
+
Class Sample
+
  Public 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
+
}}
+
#tabpage-end
+

          
+
#prompt(実行結果){{
+
1, 2, 3, 4, 5, 6, 
+
}}
+

          
+
このコードを書き換えて、double型の配列をソートできるようにすると次のようになります。
+

          
+
#tabpage(codelang=cs,container-title=クイックソートでdouble型の配列をソートするコード)
+
#code{{
+
using System;
+

          
+
public class Sample {
+
  public 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);
+
  }
+
}
+
}}
+
#tabpage(codelang=vb)
+
#code{{
+
Imports System
+

          
+
Class Sample
+
  Public 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
+
}}
+
#tabpage-end
+

          
+
#prompt(実行結果){{
+
0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 
+
}}
+

          
+
このように、扱うデータの型が変わっているだけで、それ以外のコード(ソートのアルゴリズム部分)は''全く同ものを流用することができます''。
+

          
+
そこで、このソート処理をどのような型に対しても適用できるよう、このQSortメソッドをジェネリックメソッド化することを考えます。 先のコードでソート対象のデータ型として使用していたintもしくはdoubleの個所を、ジェネリック型Tに置き換えることでジェネリックメソッド化します。
+

          
+
#tabpage(codelang=cs,container-title=データ型をパラメータ化したジェネリックなクイックソート)
+
#code{{
+
using System;
+

          
+
public class Sample {
+
  public 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);
+
  }
+
}
+
}}
+
#tabpage(codelang=vb)
+
#code{{
+
Imports System
+

          
+
Class Sample
+
  Public 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
+
}}
+
#tabpage-end
+

          
+
しかし単純に型をジェネリック型パラメータTに置き換えるだけでは上記のようにコンパイルエラーとなります。
+

          
+
intやdoubleでは比較演算子``<``が使用できるので、これによって値の大小関係を比較することができます。 一方ジェネリック型パラメータのTは、intやdoubleとなる場合があるだけでなく、比較演算子を持たない型となる場合もあります。 従って、''型Tは必ずしも比較演算子による大小関係の比較は行えない''ことから、上記のようなコンパイルエラーが発生します。
+

          
+
そのため、ジェネリック型どうしを比較するには比較演算子ではなく他の方法によって比較する必要があります。 このような目的には[[IComparer<T>インターフェイス>programming/netfx/comparison/0_comparison]]を使うことができます。 IComparer<T>インターフェイスのCompareメソッドは[[引数に指定した二つの値の大小関係に応じた戻り値を返す>programming/netfx/comparison/0_comparison#IComparer]]ので、これを比較演算子の代わりに使うことができます。 Array.Sortメソッドなども、IComparer<T>インターフェイスを指定することにより比較演算子を持たない型のソートができるようになっています。
+

          
+
比較演算子の代わりとして使用するIComparer<T>を指定できるようQSortメソッドの引数を増やし、大小関係の比較をIComparer<T>.Compareメソッドで行うように書き換えると次のようになります。
+

          
+
#tabpage(codelang=cs,container-title=IComparer<T>.Compareで値を比較するようにしたジェネリックなクイックソート)
+
#code{{
+
using System;
+
using System.Collections.Generic;
+

          
+
public class Sample {
+
  public 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);
+
  }
+
}
+
}}
+
#tabpage(codelang=vb)
+
#code{{
+
Imports System
+
Imports System.Collections.Generic
+

          
+
Class Sample
+
  Public 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
+
}}
+
#tabpage-end
+

          
+
#prompt(実行結果){{
+
0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 
+
}}
+

          
+
これにより、どのような型でもソートできるジェネリックなメソッドを作成することができました。 またソート順序を''IComparer<T>によって定義・指定できるようになる''ため、デフォルトとは異なる順序でソートしたい場合、例えば文字列をソートする際に大文字小文字の違いを無視する目的で[[StringComparer.OrdinalIgnoreCase>programming/netfx/string/2_2_compareoptions#StringComparer]]を指定する、といった使い方ができるようになります。
+

          
+
一方、比較演算子を持つintやdoubleなどの単純型でも必ずIComparer<T>を指定しなければならなくなりました。 基本型の比較を行うIComparer<T>は&msdn(netfx,member,System.Collections.Generic.Comparer`1.Default){Comparer<T>.Defaultプロパティ};を参照するだけで取得できますが、それでもこれを毎回指定するのは不便です。 そこで、次のようにIComparer<T>を指定しないオーバーロードを増やすことにより、引数の数をジェネリック化する前と同じ数にすることができます。
+

          
+
#tabpage(codelang=cs,container-title=IComparer<T>の指定を省略できるようにしたジェネリックなクイックソート)
+
#code{{
+
using System;
+
using System.Collections.Generic;
+

          
+
public class Sample {
+
  public 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);
+
  }
+
}
+
}}
+
#tabpage(codelang=vb)
+
#code{{
+
Imports System
+
Imports System.Collections.Generic
+

          
+
Class Sample
+
  Public 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
+
}}
+
#tabpage-end
+

          
+
#prompt(実行結果){{
+
0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 
+
A, a, abc, B, b, c, C, 
+
}}
+

          
+
また、IComparer<T>.Comparerメソッドと同じように[[Comparison<T>デリゲート>programming/netfx/comparison/0_comparison#Comparison]]を使うオーバーロードも増やせば、インターフェイスを実装する代わりに比較を行うメソッドやラムダ式を指定するだけでよくなるため、より使いやすくすることができます。
+

          
+
#tabpage(codelang=cs,container-title=Comparison<T>を指定できるようにしたジェネリックなクイックソート)
+
#code{{
+
using System;
+
using System.Collections.Generic;
+

          
+
public class Sample {
+
  public 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);
+
  }
+
}
+
}}
+
#tabpage(codelang=vb)
+
#code{{
+
Imports System
+
Imports System.Collections.Generic
+

          
+
Class Sample
+
  Public 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
+
}}
+
#tabpage-end
+

          
+
#prompt(実行結果){{
+
a, Aa, abc, ABC, B, bbbb, cc, 
+
B, a, cc, Aa, abc, ABC, bbbb, 
+
}}
+

          
+
ここまでで紹介したコードではすでに用意されているIComparer<T>を使用していますが、IComparer<T>を適切に実装することにより、基本型だけでなく独自に作成したクラスや構造体など任意の型のソート順や、複数キーによるソートも定義できるようになります。 IComparer<T>の実装方法などについては[[programming/netfx/comparison/0_comparison]]や[[programming/netfx/sorting/1_compositetypes]]を参照してください。
+

          
+
また、ここまでの手順と同様にしてクイックソート以外のソートアルゴリズムも実装することができます。
+

          
+

          
+
#navi(..)
+