👩🏿‍🤝‍👩🏽 🎌 🧒 .NETで並べ替え 🤹🏽 🤹🏿 🎻

ソートタスクは、プログラマーが知っておくべき古典的なタスクです。そのため、この記事がこのトピック、つまり.NETプラットフォームでの並べ替えの実装に特化した理由です。 .NETで配列を並べ替える方法について説明し、その機能、実装について説明し、Javaと少し比較します。

そのため、最初に、.NETの最初のバージョンではデフォルトのクイックソートアルゴリズムを使用します。したがって、クイックソートへの小さな余談：

利点：

最速の（実際の）汎用内部ソートアルゴリズムの1つ。
実装が簡単。
操作に必要なのはO（logn）追加メモリのみです（最悪の場合の改善された再帰アルゴリズムではなく、O（n）メモリ）。
キャッシングと仮想メモリメカニズムに適しています。

短所：

サポート要素の選択が失敗すると、速度がO（n ² ）に大幅に低下します。これは、入力が失敗すると発生する可能性があります。これは、固定的な方法ではなく、ランダムにサポート要素を選択することで回避できます。
アルゴリズムの単純な実装では、O（n）ネストされた再帰呼び出しを行う必要があるため、スタックオーバーフローエラーが発生する可能性があります。再帰呼び出しが配列の2つの部分のうち小さい方をソートするためだけの高度な実装では、再帰の深さはO（logn）を超えないことが保証されます。
不安定-安定性が必要な場合は、キーを展開する必要があります。

クイックソートアルゴリズムの単純な実装は、次のようになります。

素朴なQuickSort

public void QuickSort(int left, int right) { int l = left; int r = right; int avg = array[(l + r) / 2)]; do { while (array[l] < avg) ++l; while (array[r] > avg) --r; if (l <= r) { if (l < r) { int temp = array[l]; array[l] = array[r]; array[r] = temp; } ++l; --r; } } while (l <= r); if (left < r) QuickSort(left, r); if (l < right) QuickSort(l, right); }

上記のソートアルゴリズムには、次の欠点があります。

サポート要素は配列の中央として選択されるため、常に最大になる可能性があります。その結果、配列は長さn-1および1の2つの部分に分割され、アルゴリズム速度はO（n ² ）に低下します。
上記の条件下では、再帰の深さはO（n）に達します。その結果、nが大きい場合、ソフトウェアスタックがオーバーフローする可能性があります。
アルゴリズムは不安定です。つまり、同じ値を持つ要素を変更します。数値の並べ替えの例では、これは何の影響もありませんが、オブジェクトの配列をプロパティで並べ替えると、Sortメソッドのいくつかの呼び出しの結果、順序が異なる要素の配列が取得されるため、これは重要です。

.NETでの実装を検討します。

.NET 1.0

それでは、.NET 1.0で何が起こるか見てみましょう。先に進むと、特にユーザーが重要なタイプの場合、ここでは何も良いものが表示されないことを事前に言います...（特に一般化の欠如のため）

 public static void Sort(Array array) { Array.Sort(array, (Array) null, array.GetLowerBound(0), array.Length, (IComparer) null); } public static void Sort(Array keys, Array items, int index, int length, IComparer comparer) { if (length > 1) { if (comparer == Comparer.Default || comparer == null) { if(TrySZSort(array, null, index, index + length - 1)) { return; } } object[] keys1 = keys as object[]; object[] items1 = (object[]) null; if (keys1 != null) items1 = items as object[]; if (keys1 != null && (items == null || items1 != null)) new Array.SorterObjectArray(keys1, items1, comparer).QuickSort(index, index + length - 1); else new Array.SorterGenericArray(keys, items, comparer).QuickSort(index, index + length - 1); }

そして今、SorterObjectArrayクラスとSorterGenericArrayクラス自体：

ソーターオブジェクト配列

  private class SorterObjectArray { private object[] keys; private object[] items; private IComparer comparer; public SorterObjectArray(object[] keys, object[] items, IComparer comparer) { if (comparer == null) comparer = (IComparer)Comparer.Default; this.keys = keys; this.items = items; this.comparer = comparer; } public virtual void QuickSort(int left, int right) { do { int left1 = left; int right1 = right; object obj1 = this.keys[left1 + right1 >> 1]; do { while (this.comparer.Compare(this.keys[left1], obj1) < 0) ++left1; while (this.comparer.Compare(obj1, this.keys[right1]) < 0) --right1; if (left1 <= right1) { if (left1 < right1) { object obj2 = this.keys[left1]; this.keys[left1] = this.keys[right1]; this.keys[right1] = obj2; if (this.items != null) { object obj3 = this.items[left1]; this.items[left1] = this.items[right1]; this.items[right1] = obj3; } } ++left1; --right1; } else break; } while (left1 <= right1); if (right1 - left <= right - left1) { if (left < right1) this.QuickSort(left, right1); left = left1; } else { if (left1 < right) this.QuickSort(left1, right); right = right1; } } while (left < right); } }

SorterGenericArray

  private class SorterGenericArray { private Array keys; private Array items; private IComparer comparer; public SorterGenericArray(Array keys, Array items, IComparer comparer) { if (comparer == null) comparer = (IComparer)Comparer.Default; this.keys = keys; this.items = items; this.comparer = comparer; } public virtual void QuickSort(int left, int right) { do { int num1 = left; int num2 = right; object obj1 = this.keys.GetValue(num1 + num2 >> 1); do { while (this.comparer.Compare(this.keys.GetValue(num1), obj1) < 0) ++num1; while (this.comparer.Compare(obj1, this.keys.GetValue(num2)) < 0) --num2; if (num1 <= num2) { if (num1 < num2) { object obj2 = this.keys.GetValue(num1); this.keys.SetValue(this.keys.GetValue(num2), num1); this.keys.SetValue(obj2, num2); if (this.items != null) { object obj3 = this.items.GetValue(num1); this.items.SetValue(this.items.GetValue(num2), num1); this.items.SetValue(obj3, num2); } } ++num1; --num2; } else break; } while (num1 <= num2); if (num2 - left <= right - num1) { if (left < num2) this.QuickSort(left, num2); left = num1; } else { if (num1 < right) this.QuickSort(num1, right); right = num2; } } while (left < right); } }

ここで何が起こっているのでしょうか？次のコード

 object[] keys1 = keys as object[]; object[] items1 = (object[]) null; if (keys1 != null) items1 = items as object[];

これは配列の共分散を使用する試みに過ぎません。これはご存じのとおり、参照型に対してのみ機能します。参照型にはSorterObjectArrayクラスが使用され、重要な型にはSorterGenericArrayが使用されていることがわかります。しかし、これらのクラスはどのように異なるのでしょうか？ご覧のとおり、配列の要素にアクセスする方法のみが異なります。重要な型の場合、GetValueメソッドとSetValueメソッドが使用されますが、ご存じのように非常に遅いです...整数の配列は非常に長い時間ソートされます（結局、整数は重要なタイプです）。いや！整数の配列は、迅速かつ非常に迅速にソートされます。次のコードがすべてです

  if (length > 1) { if (comparer == Comparer.Default || comparer == null) { if(TrySZSort(array, null, index, index + length - 1)) return; } }

興味深いのはArray.TrySZSortメソッドです。このメソッドは、C ++でCLR自体に実装されているネイティブの並べ替えの実装を呼び出します。さらに、要素の比較に標準ロジックを使用する場合、つまりcomparer == Comparer.Default ||の場合、プリミティブ型に対して機能します。比較子== null。

ネイティブ実装は次のとおりです。

ネイティブTrySZSort

 FCIMPL4(INT32, ArrayHelper::TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right) //           if (keys->GetRank() != 1 || keys->GetLowerBoundsPtr()[0] != 0) return FALSE; //     TypeHandle keysTH = keys->GetElementTypeHandle(); //       const CorElementType keysElType = keysTH.GetSigCorElementType(); if (!CorTypeInfo::IsPrimitiveType(keysElType)) return FALSE; if (items != NULL) { TypeHandle itemsTH = items->GetElementTypeHandle(); if (keysTH != itemsTH) return FALSE; // Can't currently handle sorting different types of arrays. } //       if (left == right || right == 0xffffffff) return TRUE; //        ++. switch(keysElType) { case ELEMENT_TYPE_I1: // 1-    (sbyte) ArrayHelpers<I1>::QuickSort((I1*) keys->GetDataPtr(), (I1*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_U1: // 1-     (byte) case ELEMENT_TYPE_BOOLEAN: //   (bool) ArrayHelpers<U1>::QuickSort((U1*) keys->GetDataPtr(), (U1*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_I2: // 2-    (short) ArrayHelpers<I2>::QuickSort((I2*) keys->GetDataPtr(), (I2*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_U2: // 2-     (ushort) case ELEMENT_TYPE_CHAR: //   (char) ArrayHelpers<U2>::QuickSort((U2*) keys->GetDataPtr(), (U2*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_I4: // 4-    (int) ArrayHelpers<I4>::QuickSort((I4*) keys->GetDataPtr(), (I4*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_U4: // 4-     (uint) ArrayHelpers<U4>::QuickSort((U4*) keys->GetDataPtr(), (U4*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_R4: // 4-     (float) ArrayHelpers<R4>::QuickSort((R4*) keys->GetDataPtr(), (R4*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_I8: // 8-    (long) ArrayHelpers<I8>::QuickSort((I8*) keys->GetDataPtr(), (I8*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_U8: // 8-     (ulong) ArrayHelpers<U8>::QuickSort((U8*) keys->GetDataPtr(), (U8*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_R8: // 8-     (double) ArrayHelpers<R8>::QuickSort((R8*) keys->GetDataPtr(), (R8*) (items == NULL ? NULL : items->GetDataPtr()), left, right); break; case ELEMENT_TYPE_I: //       (IntPtr) case ELEMENT_TYPE_U: //         (UIntPtr) // In V1.0, IntPtr & UIntPtr are not fully supported types. They do // not implement IComparable, so searching & sorting for them should // fail. In V1.1 or V2.0, this should change. return FALSE; default: return FALSE; } return TRUE; }

ネイティブQuickSort

 // -    template <class KIND> class ArrayHelpers { static void QuickSort(KIND keys[], KIND items[], int left, int right) { do { int i = left; int j = right; KIND x = keys[(i + j) >> 1]; do { while (Compare(keys[i], x) < 0) i++; while (Compare(x, keys[j]) < 0) j--; if (i > j) break; if (i < j) { KIND key = keys[i]; keys[i] = keys[j]; keys[j] = key; if (items != NULL) { KIND item = items[i]; items[i] = items[j]; items[j] = item; } } i++; j--; } while (i <= j); if (j - left <= right - i) { if (left < j) QuickSort(keys, items, left, j); left = i; } else { if (i < right) QuickSort(keys, items, i, right); right = j; } } while (left < right); } };

ご覧のとおり、ネイティブソートはプリミティブ型に対してのみ機能します。これらには、すべての数値タイプ+論理+文字が含まれます。また、重要なユーザータイプの場合、すべてが嘆かわしいほど遅く動作します。

ソートアルゴリズム自体の実装を検討します。ネイティブ実装と重要な型の実装の両方が似ているため、SorterObjectArrayクラスでの実装を検討します。

1.配列の中央は常にサポート要素として使用されます。

 object obj1 = this.keys[left1 + right1 >> 1];

入力データが少ないと、アルゴリズムの実行時間が2次になる可能性があるため、これは良くありません。さらに、式num1 + num2 >> 1を使用して中央を取得します。これにより、int型のオーバーフローが発生する可能性があります。 Javaのバイナリ検索およびソートアルゴリズムでも同じエラーが発生しました（バグへのリンク）。

.NETの将来のバージョンでわかるように、この欠陥は修正されます。

2.スタックオーバーフローを回避するために、この実装は再帰の1つの分岐を排除する最適化を提供します。配列を分割した後、見つかった両方のサブアレイに対してパーティションプロシージャを再帰的に呼び出す代わりに、小さいサブアレイに対してのみ再帰呼び出しが行われ、大きいサブアレイがループで処理されます同じプロシージャコール内。効率の観点から見ると、平均的なケースには実質的に違いはありません。追加の再帰呼び出しのオーバーヘッドコストと、サブアレイとループの長さを比較する組織はほぼ同じです。しかし、再帰の深さは、どんな状況でもlog ₂ nを超え、最悪の場合、退化した分離の場合、通常2以下になります。すべての処理は、最初の再帰レベルのサイクルで行われます。

.NET 2.0

新しい実装には小さな変更が加えられました。一般化は.NET 2.0で登場したため、一般化された並べ替えオプションを提供します。

 public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer) { // TrySZSort      . //        Int32.CompareTo    "<"  ">". if (length <= 1 || (comparer == null || comparer == Comparer<T>.Default) && Array.TrySZSort((Array) array, (Array) null, index, index + length - 1)) return; ArraySortHelper<T>.Default.Sort(array, index, length, comparer); }

そして、これがソートする実際の方法です

クイックソート

 private static void SwapIfGreaterWithItems(T[] keys, IComparer<T> comparer, int a, int b) { if (a == b || comparer.Compare(keys[a], keys[b]) <= 0) return; T obj = keys[a]; keys[a] = keys[b]; keys[b] = obj; } internal static void QuickSort(T[] keys, int left, int right, IComparer<T> comparer) { do { int index1 = left; int index2 = right; int index3 = index1 + (index2 - index1 >> 1); ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index3); ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index2); ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index3, index2); T obj1 = keys[index3]; do { while (comparer.Compare(keys[index1], obj1) < 0) ++index1; while (comparer.Compare(obj1, keys[index2]) < 0) --index2; if (index1 <= index2) { if (index1 < index2) { T obj2 = keys[index1]; keys[index1] = keys[index2]; keys[index2] = obj2; } ++index1; --index2; } else break; } while (index1 <= index2); if (index2 - left <= right - index1) { if (left < index2) ArraySortHelper<T>.QuickSort(keys, left, index2, comparer); left = index1; } else { if (index1 < right) ArraySortHelper<T>.QuickSort(keys, index1, right, comparer); right = index2; } } while (left < right); }

汎化の存在にもかかわらず、組み込みプリミティブ型の最適化はまだそこにあると言われるべきです（開発者のコメントを参照）。つまり、プリミティブ型は依然としてネイティブの並べ替えを使用します。

参照要素は、配列の中央ではなく、配列の最初、中央、および最後の要素の中央値になりました。

 int index3 = index1 + (index2 - index1 >> 1); // ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index3); ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index2); ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index3, index2); T obj1 = keys[index3];

さらに、中央が式index1 +（index2-index1 >> 1）で計算されるようになり、オーバーフローに関連するエラーが排除されます。

それ以外の場合、すべてはまだ変更されていません。

余談ですが 、整数の配列を降順に並べ替える必要があります。どうしますか？

上記のすべてを考えると、次のコード

 Array.Sort(a); Array.Reverse(a);

私のコンピューターでは約3倍高速に動作します

 Array.Sort(a, (x, y) => -x.CompareTo(y))

Array.Reverseメソッドが一般化されていないという事実に混乱する可能性があります。つまり、意味のあるタイプ（パッケージおよびGetValue、SetValueメソッド）でゆっくりと動作しますが、その実装を見ると、組み込みの意味のあるタイプの最適化、つまり次のようなネイティブのArray.TrySZReverseメソッドを呼び出します。

逆

 template <class KIND> static void Reverse(KIND array[], UINT32 index, UINT32 count) { if (count == 0) { return; } UINT32 i = index; UINT32 j = index + count - 1; while(i < j) { KIND temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } };

一般的に、標準ライブラリでの最適化は、隅々で待っています。

ところで、このメソッドの一般化されたバージョンがないことは非常に奇妙です。 Enumerableの拡張メソッドとしてReverseメソッドがありますが、その欠点は、それが適切でないことです。ユーザーにとって重要な型の配列でArray.Reverseを呼び出すと、常に自動ボクシングが発生することがわかりました。

.NET 3.0-.NET 4.0

アルゴリズムは変更されていません。

.NET 4.5

ここから楽しみが始まります！

ただし、アルゴリズムの検討に移る前に、.NET 4.5の展開についていくつか説明する必要があります。状況を完全に理解するには、この記事を読むことをお勧めします（残念ながら、英語で）。 VS 2012、つまり.NET 4.5をインストールすると、4つのフレームワークのアセンブリが置き換えられます。実際、これは、現在.NET 4で記述している場合でも、.NET 4.5ビルドを使用していることを意味します。興味深いことに、4.5をインストールする前に1つのソートアルゴリズムを使用し、インストール後に別のアルゴリズムを使用すると、すべてが知らないうちに発生します。

実際に何が起こっているかを理解するには、.NET 4.5のコードを見てください。

 public void Sort(T[] keys, int index, int length, IComparer<T> comparer) { if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer); else ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32); }

ご覧のとおり、このメソッドは、どの.NETで作業しているかをチェックします。4.5の場合はIntrospectiveSortを使用し、4.0の場合はDepthLimitedQuickSortを使用します。

VS2012をインストールする前に、DepthLimitedQuickSortが.NET 4.0で使用された並べ替えとどのように異なるかを調べてみましょう。このメソッドのコードを見てみましょう。

DepthLimitedQuickSort

 internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit) { while (depthLimit != 0) { int index1 = left; int index2 = right; int index3 = index1 + (index2 - index1 >> 1); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index3); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index2); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index3, index2); T obj1 = keys[index3]; do { while (comparer.Compare(keys[index1], obj1) < 0) ++index1; while (comparer.Compare(obj1, keys[index2]) < 0) --index2; if (index1 <= index2) { if (index1 < index2) { T obj2 = keys[index1]; keys[index1] = keys[index2]; keys[index2] = obj2; } ++index1; --index2; } else break; } while (index1 <= index2); --depthLimit; if (index2 - left <= right - index1) { if (left < index2) ArraySortHelper<T>.DepthLimitedQuickSort(keys, left, index2, comparer, depthLimit); left = index1; } else { if (index1 < right) ArraySortHelper<T>.DepthLimitedQuickSort(keys, index1, right, comparer, depthLimit); right = index2; } if (left >= right) return; } ArraySortHelper<T>.Heapsort(keys, left, right, comparer); }

ご覧のとおり、これは1つを除いて同じクイックソートです。再帰深度（デフォルトでは32）を使い果たすと、アルゴリズムはピラミッドソートに切り替わります。

そして、ここにピラミッド型のソート自体があります：

ヒープソート

 private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer) { int n = hi - lo + 1; for (int i = n / 2; i >= 1; --i) ArraySortHelper<T>.DownHeap(keys, i, n, lo, comparer); for (int index = n; index > 1; --index) { ArraySortHelper<T>.Swap(keys, lo, lo + index - 1); ArraySortHelper<T>.DownHeap(keys, 1, index - 1, lo, comparer); } } private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer) { T x = keys[lo + i - 1]; for (; i <= n / 2; { int num; i = num;}) { num = 2 * i; if (num < n && comparer.Compare(keys[lo + num - 1], keys[lo + num]) < 0) ++num; if (comparer.Compare(x, keys[lo + num - 1]) < 0) keys[lo + i - 1] = keys[lo + num - 1]; else break; } keys[lo + i - 1] = x; }

DepthLimitedQuickSortアルゴリズムは、IntroSortにすぎません。

Introsort、または内省的ソートは、1997年にDavid Musserによって提案されたソートアルゴリズムです。 再帰の深さが事前定義されたレベルを超えると、クイックソートを使用してピラミッドソートに切り替わります。 このアプローチは、両方の方法の長所を、最悪の場合のO（n log n）およびクイックソートに匹敵するパフォーマンスと組み合わせます。 両方のアルゴリズムは比較を使用するため、このアルゴリズムは比較に基づくソートのクラスにも属します。

それでは、IntrospectiveSortで何が起こっているのか見てみましょう。実際、これは同じ内省的なソートであり、より最適化されています。ちなみに、MSDNはまだ高速ソートを使用していると言っています。

IntroSort

 private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer) { for (; hi > lo; {int num; hi = num - 1;}) { int num = hi - lo + 1; if (num <= 16) //   16    { if (num == 1) //   break; if (num == 2) //   { ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi); break; } else if (num == 3) //   { ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi - 1); ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper<T>.SwapIfGreater(keys, comparer, hi - 1, hi); break; } else { ArraySortHelper<T>.InsertionSort(keys, lo, hi, comparer); //  break; } } else if (depthLimit == 0) //    { ArraySortHelper<T>.Heapsort(keys, lo, hi, comparer); //   break; } else //      { --depthLimit; num = ArraySortHelper<T>.PickPivotAndPartition(keys, lo, hi, comparer); ArraySortHelper<T>.IntroSort(keys, num + 1, hi, depthLimit, comparer); } } }

PickPivotAndPartition

 //     private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer) { int index = lo + (hi - lo) / 2; ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, index); ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index, hi); T obj = keys[index]; ArraySortHelper<T>.Swap(keys, index, hi - 1); int i = lo; int j = hi - 1; while (i < j) { do ; while (comparer.Compare(keys[++i], obj) < 0); do ; while (comparer.Compare(obj, keys[--j]) < 0); if (i < j) ArraySortHelper<T>.Swap(keys, i, j); else break; } ArraySortHelper<T>.Swap(keys, i, hi - 1); return i; }

挿入ソート

 //  private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer) { for (int index1 = lo; index1 < hi; ++index1) { int index2 = index1; T x; for (x = keys[index1 + 1]; index2 >= lo && comparer.Compare(x, keys[index2]) < 0; --index2) keys[index2 + 1] = keys[index2]; keys[index2 + 1] = x; } }

配列での並べ替えには、挿入並べ替え、クイック並べ替え、ピラミッド並べ替えという並べ替えが混在しています。

Introsortを使用すると、実際のタスクではデータが部分的に順序付けられ、挿入によるソートがそのようなデータで非常に迅速に機能することがわかっているため、パフォーマンスにプラスの効果があります。

性能比較

Javaとの比較

ソートの点では、Javaは.NETとはまったく異なります。ただし、Javaの.NETと同様に、アルゴリズムも変更されています。

ご存じのように、高速ソートは不安定であり、これは参照タイプをソートする場合の欠点です。 Javaは「オブジェクトのようなもの」であるため、この問題は悪化するため、参照ソートのソートにはマージソートが使用されます。この並べ替えは堅牢であり、最悪の場合O（n logn）の実行時間を保証しますが、O（n）の追加メモリが必要です。

安定性の問題は参照型のみに関係するため、プリミティブでは、同じキーを持つ要素を変更するかどうかは関係ありません。そのため、Javaは改善されたクイックソートアルゴリズムDualPivotQuicksortを使用して、プリミティブをソートします。通常のクイックソートは、ランダムな要素Pを選択して配列を2つのセグメントに分割します。次に、Pより小さい要素がすべて最初のセグメントに、残りが2番目のセグメントに収まるように配列を並べ替えます。その後、アルゴリズムは最初と2番目のセグメントで再帰的に繰り返されます。 DualPivotQuicksortは、配列を2つではなく3つのセグメントに分割します。その結果、移動する配列要素の操作数が大幅に削減されます。

Java 7では、参照型をソートするアルゴリズムがTimSortに変更されました。

Timsortは、2002年にTim Petersが公開した、挿入ソートとマージソートを組み合わせたハイブリッドソートアルゴリズムです。 Timsortは現在、Python、OpenJDK 7の標準のソートアルゴリズムであり、Android JDK 1.5に実装されています。 アルゴリズムの主なアイデアは、現実の世界では、ソートされたデータ配列に順序付きサブ配列が含まれることが多いということです。 このようなデータにより、Timsortは多くのソートアルゴリズムよりも大幅に高速です。

ティムソートは高速ですが、ランダムデータでは高速ソートよりも約30％劣っています。

2つのフレームワークでのソートの実装におけるこの違いをどう思いますか？メモリに費やす必要のある実際のタスクに安定性が本当に必要なのか、それはJavaでどのように行われるのか？または、.NETで行われている速度とメモリの節約と引き換えに、安定性なしで実行できますか？個人的には、.NETを選択します。安定性は、発生する特定のタスクでのみ必要であり、それほど頻繁ではないため、少なくとも4年以上は立ち上がっていないためです。問題はプログラマの肩にかかる可能性があります。安定したソートアルゴリズムを実装することは難しくないと思います。

おわりに

おそらく、すべてのプログラマーが.NETについてそのような詳細を必要とするわけではありませんが、彼らの知識は誰も傷つけないと思います。洗練されたインタビュアーは、面接でのソートについて質問することもできます。一般的に、読んでくれてありがとう。この記事がお役に立てば幸いです。

.NETで並べ替え