wizaman's blog (legacy) これまでC#の安定ソートが欲しくて色々と検討していました。
アロケーションを気にしなければ、LinkedListについては各要素にインデックス振ったListを作ってSort()するのが速いという結果が出ていました。その実装をここにまとめます。List版もありますが、先の記事で検討したマージソートの方が速いので、Listではそっちを使ったほうがいいです。性能比較については前回の記事を参照。
実装
インデックスと値のペアであるIndexedValueを値型（struct）で定義し、IndexedValueのListをSort()します。このListに詰め込む元はIEnumerableにしているので、IndexedValueのソート済みリストに変換する、というのが基本処理です。
配列、List、LinkedListには個別対応として、拡張メソッドstableSort()を定義することで、普段のSort()と同じような感覚で使えるようにしてあります。また、IndexedValueのリストからの変換も用意しています。
特にLinkedListには標準でソート機能が提供されていないので、LinkedListのソートが欲しい人にも需要あるかと。
public class FunctorComparer<T> : IComparer<T>
{
public FunctorComparer(Comparison<T> comparison)
{
_comparison = comparison;
}
public int Compare(T x, T y)
{
return _comparison(x, y);
}
private Comparison<T> _comparison = null;
}public static class StableSort
{
#region 内部クラス
public struct IndexedValue<T>
{
public int index;
public T value;
public IndexedValue(int index, T value)
{
this.index = index;
this.value = value;
}
}
public class IndexedComparer<T> : IComparer<IndexedValue<T>>
{
public IComparer<T> comparer;
public IndexedComparer(IComparer<T> comparer = null)
{
if(comparer == null) {
comparer = Comparer<T>.Default;
}
this.comparer = comparer;
}
public int Compare(IndexedValue<T> x, IndexedValue<T> y)
{
var result = comparer.Compare(x.value, y.value);
if(result != 0) {
return result;
}
return x.index - y.index;
}
}
#endregion
#region リスト変換
public static T[] toArray<T>(this List<IndexedValue<T>> indexedList)
{
var array = new T[indexedList.Count];
var count = indexedList.Count;
for(var i = 0; i < count; ++i) {
var value = indexedList[i].value;
array[i] = value;
}
return array;
}
public static List<T> toList<T>(this List<IndexedValue<T>> indexedList)
{
var list = new List<T>(indexedList.Count);
var count = indexedList.Count;
for(var i = 0; i < count; ++i) {
var value = indexedList[i].value;
list.Add(value);
}
return list;
}
public static LinkedList<T> toLinkedList<T>(this List<IndexedValue<T>> indexedList)
{
var list = new LinkedList<T>();
var count = indexedList.Count;
for(var i = 0; i < count; ++i) {
var value = indexedList[i].value;
list.AddLast(value);
}
return list;
}
public static IEnumerable<T> toValues<T>(this List<IndexedValue<T>> indexedList)
{
foreach(var indexed in indexedList) {
yield return indexed.value;
}
}
public static List<IndexedValue<T>> toIndexedList<T>(this IEnumerable<T> values)
{
var collection = values as ICollection<T>;
List<IndexedValue<T>> list = null;
if(collection != null) {
list = new List<IndexedValue<T>>(collection.Count);
} else {
list = new List<IndexedValue<T>>();
}
var i = 0;
foreach(var value in values) {
list.Add(new IndexedValue<T>(i, value));
++i;
}
return list;
}
#endregion
#region インデックス付きリストのソート
public static void sort<T>(this List<IndexedValue<T>> list)
{
sort(list, 0, list.Count, null);
}
public static void sort<T>(this List<IndexedValue<T>> list, Comparison<T> comparison)
{
if(list.Count <= 1) return;
sort(list, new FunctorComparer<T>(comparison));
}
public static void sort<T>(this List<IndexedValue<T>> list, IComparer<T> comparer)
{
sort(list, 0, list.Count, comparer);
}
public static void sort<T>(this List<IndexedValue<T>> list, int index, int count, IComparer<T> comparer)
{
if(list.Count <= 1) return;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
list.Sort(new IndexedComparer<T>(comparer));
}
#endregion
#region ソート済みインデックス付きリストの取得
public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values)
{
IComparer<T> comparer = null;
return toSortedList(values, comparer);
}
public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values, Comparison<T> comparison)
{
IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
return toSortedList(values, comparer);
}
public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values, IComparer<T> comparer)
{
var list = values.toIndexedList();
if(list.Count <= 1) return list;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
list.sort(comparer);
return list;
}
public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values, int index, int count, IComparer<T> comparer)
{
var list = values.toIndexedList();
if(list.Count <= 1) return list;
if(comparer == null) {
comparer = Comparer<T>.Default;
}
list.Sort(new IndexedComparer<T>(comparer));
return list;
}
#endregion
#region T[]の安定ソート
public static void stableSort<T>(this T[] array)
{
stableSort(array, 0, array.Length, null);
}
public static void stableSort<T>(this T[] array, Comparison<T> comparison)
{
stableSort(array, new FunctorComparer<T>(comparison));
}
public static void stableSort<T>(this T[] array, IComparer<T> comparer)
{
stableSort(array, 0, array.Length, comparer);
}
public static void stableSort<T>(this T[] array, int index, int count, IComparer<T> comparer)
{
var sortedList = array.toSortedList(index, count, comparer);
for(var i = 0; i < count; ++i) {
array[index + i] = sortedList[i].value;
}
}
#endregion
#region List<T>の安定ソート
public static void stableSort<T>(this List<T> list)
{
stableSort(list, 0, list.Count, null);
}
public static void stableSort<T>(this List<T> list, Comparison<T> comparison)
{
stableSort(list, new FunctorComparer<T>(comparison));
}
public static void stableSort<T>(this List<T> list, IComparer<T> comparer)
{
stableSort(list, 0, list.Count, comparer);
}
public static void stableSort<T>(this List<T> list, int index, int count, IComparer<T> comparer)
{
var sortedList = list.toSortedList(index, count, comparer);
list.Clear();
list.AddRange(sortedList.toValues());
}
#endregion
#region LinkedList<T>の安定ソート
public static void stableSort<T>(this LinkedList<T> list)
{
stableSort(list, 0, list.Count, null);
}
public static void stableSort<T>(this LinkedList<T> list, Comparison<T> comparison)
{
stableSort(list, new FunctorComparer<T>(comparison));
}
public static void stableSort<T>(this LinkedList<T> list, IComparer<T> comparer)
{
stableSort(list, 0, list.Count, comparer);
}
public static void stableSort<T>(this LinkedList<T> list, int index, int count, IComparer<T> comparer)
{
var sortedList = list.toSortedList(index, count, comparer);
list.Clear();
for(var i = 0; i < count; ++i) {
list.AddLast(sortedList[i].value);
}
}
#endregion
}