🎐 🍬 🧙🏼 .NET में सॉर्ट करें 🕕 🤶 🚴🏿

सॉर्टिंग कार्य एक क्लासिक कार्य है जिसे किसी भी प्रोग्रामर को पता होना चाहिए। यही कारण है कि यह लेख इस विषय के लिए समर्पित है - .NET प्लेटफ़ॉर्म पर छंटनी का कार्यान्वयन। मैं चाहता हूं कि .NET में काम करने वाले एरियर्स कैसे काम करते हैं, इसके फीचर्स, इम्प्लीमेंटेशन के बारे में बात करना चाहते हैं और जावा के साथ थोड़ी तुलना भी करते हैं।

तो, के साथ शुरू करने के लिए, .NET के पहले संस्करण डिफ़ॉल्ट त्वरित सॉर्ट एल्गोरिथ्म का उपयोग करते हैं। इसलिए, त्वरित छँटाई में एक छोटा विषयांतर:

लाभ:

सामान्य-उद्देश्य वाले आंतरिक सॉर्टिंग एल्गोरिदम का सबसे तेज़ (अभ्यास में);
लागू करने में आसान;
इसके संचालन के लिए केवल O (logn) अतिरिक्त मेमोरी की आवश्यकता होती है (सबसे खराब स्थिति में एक बेहतर पुनरावर्ती एल्गोरिथ्म नहीं, O (n) मेमोरी);
यह कैशिंग और वर्चुअल मेमोरी तंत्र के साथ अच्छी तरह से चला जाता है।

नुकसान:

यह सहायक तत्वों के असफल विकल्पों के साथ O (n ² ) की गति में बहुत गिरावट लाता है, जो असफल इनपुट के साथ हो सकता है। बेतरतीब ढंग से समर्थन तत्व चुनकर इससे बचा जा सकता है, न कि निश्चित तरीके से;
एल्गोरिथ्म के एक भोले-भाले कार्यान्वयन से स्टैक ओवरफ्लो त्रुटि हो सकती है, क्योंकि इसमें O (n) नेस्टेड रिर्सिव कॉल करने की आवश्यकता हो सकती है। बेहतर कार्यान्वयन में, जिसमें एक पुनरावर्ती कॉल केवल सरणी के दो हिस्सों में से छोटे को सॉर्ट करने के लिए किया जाता है, पुनरावृत्ति की गहराई को O (logn) से अधिक नहीं होने की गारंटी है;
अस्थिर - यदि स्थिरता की आवश्यकता है, तो आपको कुंजी का विस्तार करना होगा।

एक त्वरित सॉर्ट एल्गोरिथ्म का एक भोली कार्यान्वयन कुछ इस तरह लग सकता है:

Naive 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 के दो भागों में विभाजित किया जाएगा और एल्गोरिथ्म गति O (n ² ) तक नीचा हो जाएगी;
उपरोक्त शर्तों के तहत, पुनरावृत्ति की गहराई ओ (एन) तक पहुंचती है, जिसके परिणामस्वरूप, बड़े एन के लिए, सॉफ्टवेयर स्टैक ओवरफ्लो हो सकता है;
एल्गोरिथ्म अस्थिर है, अर्थात, यह समान मूल्यों के साथ तत्वों को बदलता है। सॉर्टिंग नंबरों के उदाहरण पर, यह हमें किसी भी तरह से प्रभावित नहीं करता है, लेकिन अगर हम किसी भी संपत्ति द्वारा वस्तुओं की एक सरणी को सॉर्ट करते हैं, तो यह महत्वपूर्ण है, क्योंकि सॉर्ट विधि के लिए कई कॉल के परिणामस्वरूप हमें ऐसे तत्वों की एक सरणी मिलेगी, जिनका क्रम अलग है।

हम .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 स्वयं कक्षाएं:

SorterObjectArray

  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[];

यह सरणियों के सहसंयोजक का उपयोग करने के प्रयास से अधिक कुछ नहीं है, जो कि जैसा कि आप जानते हैं, केवल संदर्भ प्रकारों के लिए काम करता है। यह पता चला है कि सॉर्टरऑब्जेक्टअरे वर्ग का उपयोग संदर्भ प्रकारों के लिए किया जाता है, और सॉर्टरगेंरिकेरियर का उपयोग महत्वपूर्ण प्रकारों के लिए किया जाता है। लेकिन रुकिए, ये वर्ग अलग कैसे हैं? जैसा कि आप देख सकते हैं, वे केवल सरणी के तत्वों तक पहुंचने के तरीके में भिन्न होते हैं। महत्वपूर्ण प्रकारों के लिए, GetValue और SetValue विधियों का उपयोग किया जाता है, जो कि आप जानते हैं, बहुत धीमी गति से हैं ... यह पता चला है कि पूर्णांकों की सरणी बहुत लंबे समय तक छंटेगी (आखिरकार, पूर्णांक एक महत्वपूर्ण प्रकार है)? नहीं! पूर्णांकों की एक सरणी को जल्दी और बहुत जल्दी हल किया जाता है। यह निम्नलिखित कोड के बारे में है

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

ब्याज की Array.TrySZSort विधि है। यह विधि C ++ में C ++ में लागू मूल सॉर्टिंग कार्यान्वयन को कॉल करती है। इसके अलावा, यह आदिम प्रकारों के लिए काम करता है जब हम तत्वों की तुलना करने के लिए मानक तर्क का उपयोग करते हैं, अर्थात, जब = = Comparer.Default || तुलनित्र == अशक्त।

और यहाँ मूल कार्यान्वयन है:

मूल निवासी 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; }

नेटिव क्विकॉर्ट

 // -    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];

यह अच्छा नहीं है, क्योंकि खराब इनपुट डेटा के साथ, एल्गोरिथ्म का निष्पादन समय द्विघात हो सकता है। इसके अलावा, बीच को फॉर्मूला num1 + num2 >> 1 के अनुसार लिया जाता है, जिससे टाइप int का ओवरफ्लो हो सकता है। जावा में बाइनरी सर्च और सॉर्टिंग एल्गोरिदम में एक ही त्रुटि की गई थी ( बग से लिंक )।

जैसा कि आप .NET के भविष्य के संस्करणों में देखेंगे, यह दोष ठीक हो जाएगा।

2. स्टैक ओवरफ्लो से बचने के लिए, यह कार्यान्वयन अनुकूलन प्रदान करता है जो पुनरावृत्ति की एक शाखा को समाप्त करता है: सरणी को विभाजित करने के बाद दोनों पाए गए उप-भागों के लिए विभाजन प्रक्रिया को पुन: कॉल करने के बजाय, एक पुनरावर्ती कॉल केवल छोटे उप-वर्ग के लिए किया जाता है, और बड़ा एक लूप में संसाधित होता है। एक ही प्रक्रिया कॉल के भीतर। दक्षता के दृष्टिकोण से, औसत मामले में व्यावहारिक रूप से कोई अंतर नहीं है: एक अतिरिक्त पुनरावर्ती कॉल की ओवरहेड लागत और उप-लंबाई और लूप की लंबाई की तुलना करने के संगठन के समान क्रम के बारे में हैं। लेकिन पुनरावृत्ति की गहराई, किसी भी परिस्थिति में, लॉग ₂ एन से अधिक नहीं होगी, और पतित अलगाव के सबसे खराब मामले में, यह आम तौर पर 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); }

और यहाँ वास्तविक विधि है जो सॉर्ट करती है

quicksort

 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 विधि सामान्यीकृत नहीं है, जिसका अर्थ है कि यह धीरे-धीरे सार्थक प्रकारों (पैकेजिंग और गेटवैल्यू, सेटवैल्यू विधियों) के साथ काम करेगा, लेकिन यदि आप इसके कार्यान्वयन को देखते हैं तो हम फिर से अंतर्निहित सार्थक प्रकारों के लिए अनुकूलन करेंगे, अर्थात् देशी 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 के लिए एक विस्तार विधि के रूप में एक रिवर्स विधि है, लेकिन इसकी खामी यह है कि यह जगह से बाहर करता है। यह पता चला है कि Array.Reverse को उपयोगकर्ता-महत्वपूर्ण प्रकारों की एक सरणी पर कॉल करना हमेशा ऑटो-बॉक्सिंग की ओर जाता है।

.NET 3.0 - .NET 4.0

एल्गोरिथ्म नहीं बदला है।

.NET 4.5

मज़ा यहाँ शुरू होता है!

लेकिन एल्गोरिथ्म पर विचार करने से पहले, मुझे .NET 4.5 की तैनाती के बारे में कुछ शब्द कहने चाहिए। स्थिति की पूरी समझ के लिए, मैं आपको यह लेख (दुर्भाग्य से, अंग्रेजी में) पढ़ने की सलाह देता हूं। वीएस 2012 स्थापित करते समय, अर्थात .NET 4.5 को स्थापित करते समय, यह 4 फ्रेमवर्क की असेंबली को बदल देता है। वास्तव में, इसका मतलब है कि जब आप अब .NET 4 में लिख रहे हैं, तब भी आप .NET 4.5 बिल्ड का उपयोग कर रहे हैं। यह एक दिलचस्प बात निकलती है: 4.5 स्थापित करने से पहले, आप एक छँटाई एल्गोरिथ्म का उपयोग करते हैं, स्थापना के बाद आप एक अलग एल्गोरिथ्म का उपयोग करते हैं, और सब कुछ आपके ज्ञान के बिना होता है।

वास्तव में क्या चल रहा है यह समझने के लिए, .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।

आइए जानें कि वीएस 2012 स्थापित करने से पहले .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); }

जैसा कि आप देख सकते हैं, यह एक को छोड़कर एक ही त्वरित सॉर्ट है: एल्गोरिथ्म पिरामिड की तरह स्विच करता है यदि हम पुनरावृत्ति की गहराई को समाप्त करते हैं, जो कि डिफ़ॉल्ट रूप से 32 है।

और यहाँ पिरामिड की खुद की छँटाई है:

Heapsort

 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 से ज्यादा कुछ नहीं है।

इंट्रोसोर्ट, या आत्मनिरीक्षण छँटाई, 1997 में डेविड मूसर द्वारा प्रस्तावित एक छँटाई एल्गोरिथ्म है। जब पुनरावृत्ति की गहराई कुछ पूर्वनिर्धारित स्तर से अधिक हो जाती है तो यह पिरामिड सॉर्टिंग के लिए त्वरित छँटाई और स्विच का उपयोग करता है। यह दृष्टिकोण सबसे खराब स्थिति हे (एन लॉग एन) और प्रदर्शन की तुलना में दोनों तरीकों की ताकत को जोड़ता है। चूंकि दोनों एल्गोरिदम तुलनाओं का उपयोग करते हैं, इसलिए यह एल्गोरिदम भी तुलना आधारित सॉर्टिंग के वर्ग के अंतर्गत आता है।

अब देखते हैं कि इंट्रोस्पेक्टिवसॉर्ट में क्या हो रहा है। वास्तव में, यह एक ही आत्मनिरीक्षण छँटाई है, केवल अधिक अनुकूलित। वैसे, 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; }

InsertionSort

 //  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 .NET से काफी अलग है। हालाँकि, जावा में .NET के रूप में, एल्गोरिथ्म भी बदल गया है।

जैसा कि आप जानते हैं, तेजी से छँटाई अस्थिर है, जो संदर्भ प्रकारों को छांटते समय एक नुकसान है। चूँकि जावा “ऑब्जेक्ट की तरह” है, इसलिए यह समस्या बढ़ जाती है, इसलिए मर्ज सॉर्ट का उपयोग संदर्भ प्रकारों को सॉर्ट करने के लिए किया जाता है। यह छँटाई मजबूत है और सबसे खराब स्थिति में O (n logn) रन टाइम की गारंटी देता है, हालाँकि, इसके लिए O (n) अतिरिक्त मेमोरी की आवश्यकता होती है।

चूंकि स्थिरता की समस्या केवल संदर्भ प्रकारों की चिंता करती है, इसलिए यह प्राथमिकताओं के लिए कोई फर्क नहीं पड़ता कि हम तत्वों को एक ही कुंजी के साथ बदलते हैं या नहीं। इसलिए, आदिमों को सॉर्ट करने के लिए जावा एक बेहतर क्विक सॉर्ट अल्गोरिथम, ड्यूलपॉइंटक्विस्कॉर्ट का उपयोग करता है। सामान्य क्विकॉर्ट ने सरणी को दो खंडों में विभाजित किया है, एक यादृच्छिक तत्व पी। तब यह सरणी को सॉर्ट करता है ताकि पी से कम सभी तत्व पहले खंड में और बाकी दूसरे में गिरे। फिर एल्गोरिथ्म पहले और दूसरे खंड पर पुनरावृत्ति दोहराता है। DualPivotQuicksort दो के बजाय सरणी को तीन खंडों में विभाजित करता है। परिणामस्वरूप, चलती सरणी तत्वों के संचालन की संख्या काफी कम हो जाती है।

जावा 7 में, संदर्भ प्रकारों को सॉर्ट करने के लिए एल्गोरिथ्म टिमसॉर्ट में बदल गया है।

Timsort एक हाइब्रिड सॉर्टिंग एल्गोरिथ्म है जो 2002 में टिम पीटर्स द्वारा प्रकाशित प्रविष्टि सॉर्टिंग और मर्ज सॉर्टिंग को मिलाता है। Timsort वर्तमान में Python, OpenJDK 7 में मानक सॉर्टिंग एल्गोरिदम है, और Android JDK 1.5 में लागू किया गया है। एल्गोरिथ्म का मुख्य विचार यह है कि वास्तविक दुनिया में, सॉर्ट किए गए डेटा सरणियों में अक्सर आदेशित सबरेज़ होते हैं। ऐसे डेटा के साथ, कई सॉर्टिंग एल्गोरिदम की तुलना में टिम्सॉर्ट काफी तेज है।

Timsort तेज़ है, लेकिन यादृच्छिक डेटा पर यह तेज़ छँटाई के बारे में 30 प्रतिशत हीन है।

दो ढाँचों में छँटाई के कार्यान्वयन में इस अंतर के बारे में आप क्या सोचते हैं? क्या हमें वास्तव में वास्तविक जीवन के कार्यों में स्थिरता की आवश्यकता है जो स्मृति पर खर्च करने की आवश्यकता है, और यह जावा में कैसे किया जाता है? या आप स्थिरता के बिना कर सकते हैं, गति और मेमोरी सेविंग के बदले में जैसा कि .NET में किया जाता है? व्यक्तिगत रूप से, मैं अपनी पसंद .NET को देता हूं, क्योंकि मुझे लगता है कि केवल कुछ कार्यों में ही स्थिरता की आवश्यकता होती है, ऐसा अक्सर नहीं होता है, कम से कम मैं 4 साल से अधिक समय तक नहीं आता, ठीक है, और अगर इस तरह का कोई समाधान है , , .

निष्कर्ष

.NET , , . , . , . मुझे उम्मीद है कि यह लेख मददगार रहा है।

.NET में सॉर्ट करें