तेजी से छंटनी वास्तव में धीमी क्यों है? नई ऐरे सॉर्ट विधि

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

इसके आधार पर, मैंने एक सरणी को सॉर्ट करने के लिए अपना एल्गोरिथम लिखने का फैसला किया, जो कि quick_sort से बेहतर काम करेगा। और अगर सरणी पहले से ही सॉर्ट की गई है, तो इसे बार का एक गुच्छा न चलाएं, जैसा कि कई एल्गोरिदम के मामले में है।

"यह शाम थी, वहाँ कुछ नहीं करना था," सर्गेई मिखालकोव।

आवश्यकताएँ:

1. सबसे अच्छा मामला हे (एन)
2. ओ का औसत मामला (एन लॉग एन)
3. सबसे खराब स्थिति हे (एन लॉग एन)
4. त्वरित छँटाई की तुलना में तेजी से औसत पर

अब चलो यह सब क्रम में मिलता है

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

प्रारंभिक जानकारी

int* glue(int* a, int lenA, int* b, int lenB) { int lenC = lenA + lenB; int* c = new int[lenC]; //   int indx_a = 0; int indx_b = 0; int i = 0; for (; i < lenC; ++i) { if (indx_a < lenA) { if (indx_b < lenB) { //     c[i] = (a[indx_a] < b[indx_b]) ? a[indx_a++] : b[indx_b++]; continue; } //      while (indx_a < lenA) c[i++] = a[indx_a++]; } else //      while (indx_b < lenB) c[i++] = b[indx_b++]; break; } return c; } 

 void glueDelete(int*& arr, int*& a, int lenA, int*& b, int lenB) { if (lenA == 0) { //    delete[] a; //     arr = b; //     return; } if (lenB == 0) { //    delete[] b; //     arr = a; //     return; } int *copy = glue(a, lenA, b, lenB); //  delete[]a; //    delete[]b; //    arr = copy; //   } 

 void insertionSort(int*& arr, int lo, int hi) { for (int i = lo + 1; i <= hi; ++i) for (int j = i; j > 0 && arr[j - 1] > arr[j]; --j) swap(arr[j - 1], arr[j]); } 

एल्गोरिथ्म का प्रारंभिक संस्करण (इष्टतम नहीं):

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

इनपुट फ़ंक्शन इस सरणी में एक सरणी और तत्वों की संख्या लेता है

 void FirstNewGeneratingSort(int*& arr, int len) 

सरणी (हमारे उच्च और चढ़ाव) और अन्य तत्वों से एक नमूना संग्रहीत करने के लिए, हम स्मृति आवंटित करते हैं

 int* selection = new int[len << 1]; //     new int[len * 2] int left = len - 1; //       int right = len; //       int* restElements = new int[len]; //  ,      int restLen = 0; //      

जैसा कि आप देख सकते हैं, हमने अपने मूल सरणी की तुलना में नमूने को संग्रहीत करने के लिए 2 गुना अधिक मेमोरी आवंटित की है। यह उस स्थिति में किया जाता है जब हमारे पास एक सरणी होती है और प्रत्येक अगला तत्व एक नया अधिकतम होगा। तब नमूना सरणी के केवल दूसरे भाग पर कब्जा कर लिया जाएगा। या इसके विपरीत (यदि अवरोही क्रम में क्रमबद्ध हो)।

नमूना लेने के लिए, आपको पहले प्रारंभिक न्यूनतम और अधिकतम की आवश्यकता है। बस पहले और दूसरे तत्वों का चयन करें

 if (arr[0] > arr[1]) swap(arr[0], arr[1]); selection[left--] = arr[0]; selection[right++] = arr[1]; 

खुद का नमूना लेना

 for (int i = 2; i < len; ++i) { if (selection[right - 1] <= arr[i]) //     { selection[right++] = arr[i]; continue; } if (selection[left + 1] >= arr[i]) //     { selection[left--] = arr[i]; continue; } restElements[restLen++] = arr[i]; //      ,    } 

अब हमारे पास तत्वों का एक सॉर्ट सेट है, और "शेष" तत्व जिन्हें हमें अभी भी सॉर्ट करने की आवश्यकता है। लेकिन पहले आपको कुछ मेमोरी हेरफेर करने की आवश्यकता है।

अप्रयुक्त स्मृति को मुक्त करें

 int selectionLen = right - left - 1; //   int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); //       delete[] selection; //   2 * len ,         ,     selection = copy; //  ,    selection     delete[] arr; //    ,         ,       

शेष तत्वों के लिए एक पुनरावर्ती सॉर्ट कॉल करें और उन्हें चयन के साथ मर्ज करें

 FirstNewGeneratingSort(restElements, restLen); glueDelete(arr, selection, selectionLen, restElements, restLen); 

 void FirstNewGeneratingSort(int*& arr, int len) { if (len < 2) return; int* selection = new int[len << 1]; int left = len - 1; int right = len; int* restElements = new int[len]; int restLen = 0; if (arr[0] > arr[1]) swap(arr[0], arr[1]); selection[left--] = arr[0]; selection[right++] = arr[1]; for (int i = 2; i < len; ++i) { if (selection[right - 1] <= arr[i]) //     { selection[right++] = arr[i]; continue; } if (selection[left + 1] >= arr[i]) //     { selection[left--] = arr[i]; continue; } restElements[restLen++] = arr[i]; //      ,    } int selectionLen = right - left - 1; //   int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); //       delete[] selection; //   2 * len ,          ,     selection = copy; //  ,    selection     delete[] arr; //    ,         ,       FirstNewGeneratingSort(restElements, restLen); glueDelete(arr, selection, selectionLen, restElements, restLen); } 

आइए क्विक सॉर्ट की तुलना में एल्गोरिथ्म की गति की जांच करें

जैसा कि आप देख सकते हैं, यह बिल्कुल नहीं है जो हम चाहते थे। QuickSort की तुलना में लगभग 6 गुना लंबा! लेकिन इस संदर्भ में कई बार इसका उपयोग करना अनुचित है, क्योंकि यहाँ यह अस्मितावादी है जो मायने रखता है। एल्गोरिथम के इस कार्यान्वयन में, सबसे खराब स्थिति में, पहला और दूसरा तत्व न्यूनतम और अधिकतम होगा। और बाकी को एक अलग सरणी में कॉपी किया जाएगा।

एल्गोरिथम जटिलता:

• सबसे खराब स्थिति: O (n ² )
• मध्य का मामला: O (n ² )
• सबसे अच्छा मामला: O (n)

हम्म, यह आवेषण द्वारा समान छंटनी से बेहतर नहीं है। हां, वास्तव में हम अधिकतम (न्यूनतम) तत्व बहुत जल्दी पा सकते हैं, और बाकी बस चयन में नहीं आएंगे।

हम मर्ज सॉर्ट को ऑप्टिमाइज़ करने का प्रयास कर सकते हैं। सबसे पहले, सामान्य मर्ज सॉर्ट की गति जांचें:

 void newGenerationMergeSort(int* a, int lo, int hi, int& minPortion) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; if (hi - lo <= minPortion) { //       ,     int* part = glue(a + lo, hi - lo + 1, nullptr, 0); //    FirstNewGeneratingSort(part, hi - lo + 1); for (int i = lo; i <= hi; ++i) { a[i] = part[i - lo]; } delete[] part; return; } newGenerationMergeSort(a, lo, mid, minPortion); newGenerationMergeSort(a, mid + 1, hi, minPortion); int* b = glue(a + lo, mid - lo + 1, a + mid + 1, hi - mid); for (int i = lo; i <= hi; i++) a[i] = b[i - lo]; delete[] b; } 

उपयोग में आसानी के लिए किसी प्रकार के आवरण की आवश्यकता होती है।

 void newMergeSort(int *arr, int length) { int portion = log2(length); //      portion *= portion; newGenerationMergeSort(arr, 0, length - 1, portion); } 

परीक्षा परिणाम:

हां, गति में वृद्धि देखी जाती है, लेकिन फिर भी, यह फ़ंक्शन क्विक सॉर्ट के रूप में तेजी से काम नहीं करता है। इसके अलावा, हम सॉर्ट किए गए सरणियों पर O (n) के बारे में बात नहीं कर सकते। इसलिए, यह विकल्प भी छोड़ दिया गया है।

पहले विकल्प के लिए अनुकूलन विकल्प

1. जटिलता के लिए ओ (एन ² ) नहीं होने के लिए, हम उन तत्वों को जोड़ सकते हैं जो पहले की तरह 1 सरणी में नहीं थे, लेकिन उन्हें 2 सरणियों में विस्तारित करें। उसके बाद, यह केवल इन दो भागों को सॉर्ट करने के लिए रहता है, और उन्हें हमारे नमूने के साथ मर्ज करता है। परिणामस्वरूप, हमें O के बराबर जटिलता मिलती है (n log n)

2. जैसा कि हमने पहले ही देखा है, क्रमबद्ध सरणी में बिल्कुल अधिकतम (न्यूनतम) तत्व काफी जल्दी मिल सकता है, और यह बहुत प्रभावी नहीं है। यह वह जगह है जहाँ प्रविष्टि सॉर्टिंग हमारी मदद के लिए आती है। चयन के प्रत्येक पुनरावृत्ति पर, हम जाँचेंगे कि क्या हम प्रवाह तत्व को अंतिम के एक सेट में सम्मिलित कर सकते हैं, उदाहरण के लिए, आठ सम्मिलित हैं।

यदि यह अभी स्पष्ट नहीं है, तो परेशान न हों। ऐसा होना चाहिए। अब कोड पर सब कुछ स्पष्ट हो जाएगा और प्रश्न गायब हो जाएंगे।

एल्गोरिथ्म का अवशिष्ट सही संस्करण:

हस्ताक्षर पिछले संस्करण की तरह ही है

 void newGenerationSort(int*& arr, int len) 

लेकिन यह ध्यान दिया जाना चाहिए कि यह विकल्प एक संकेतक को पहले पैरामीटर पर मानता है, जिस पर डिलीट [] ऑपरेशन कहा जा सकता है (क्यों - हम बाद में देखेंगे)। यही है, जब हमने मेमोरी आवंटित की, तो हमने इस पॉइंटर के लिए सरणी की शुरुआत का पता सौंपा।

प्रारंभिक तैयारी

इस उदाहरण में, तथाकथित "कैच अप गुणांक" केवल 8 के मान के साथ एक स्थिर है। यह दर्शाता है कि हम कितने नए "अंडर-मैक्सिमेंट" या "अंडर-मिनिमम" को इसके स्थान पर डालने के लिए कितने अधिकतम तत्वों के माध्यम से जाने की कोशिश करते हैं।

 int localCatchUp = min(catchUp, len); //            insertionSort(arr, 0, localCatchUp - 1); //     localCatchUp  if (len <= localCatchUp) //       n <= catchUp ,   return; //    (      ) 

नमूना संग्रहीत करने के लिए, एक सरणी बनाएं

यदि कुछ स्पष्ट नहीं है, तो प्रारंभिक संस्करण में स्पष्टीकरण देखें

 int* selection = new int[len << 1]; //     new int[len * 2] int left = len - 1; //       int right = len; //       

चयन सरणी के पहले कुछ तत्वों को भरें

 selection[left--] = arr[0]; for (int i = 1; i < localCatchUp; ++i) { selection[right++] = arr[i]; } 

मैं आपको याद दिलाता हूं कि नए सरणी नमूना सरणी के केंद्र के बाईं ओर जाते हैं, और नई ऊंचे दाईं ओर जाते हैं

अचयनित वस्तुओं को संग्रहीत करने के लिए सरणियाँ बनाएँ

 int restLen = len >> 1; //     len / 2 int* restFirst = new int[restLen]; int* restSecond = new int[restLen]; int restFirstLen = 0; int restSecondLen = 0; 

अब, सबसे महत्वपूर्ण बात स्रोत सरणी से तत्वों का सही चयन है

चक्र लोकलचेकअप से शुरू होता है (क्योंकि पिछले तत्व पहले ही हमारे नमूने में प्रवेश कर चुके हैं, जहाँ से हम शुरू करेंगे)। और यह अंत तक जाता है। इसलिए, अंत में, सभी तत्वों को या तो चयन सरणी में या अंडर-चयन सरणियों में वितरित किया जाएगा।

यह जाँचने के लिए कि क्या हम किसी तत्व को चयन में सम्मिलित कर सकते हैं, हम बस यह जाँचेंगे कि क्या यह तत्व (या बराबर) तत्व के 8 पदों पर बाईं (दाईं ओर - लोकलचैप) है। यदि यह मामला है, तो हम बस इन तत्वों के माध्यम से एक पास के साथ वांछित स्थिति में डालते हैं। यह दाईं ओर के लिए था, यानी अधिकतम तत्वों के लिए। उसी तरह, हम कम से कम लोगों के लिए रिवर्स करते हैं। यदि आप इसे चयन के दोनों ओर सम्मिलित नहीं करते हैं, तो हम इसे शेष सरणियों में से एक में फेंक देते हैं।

लूप कुछ इस तरह दिखेगा:

 for (int i = localCatchUp; i < len; ++i) { if (selection[right - localCatchUp] <= arr[i]) { selection[right] = arr[i]; for (int j = right; selection[j - 1] > selection[j]; --j) swap(selection[j - 1], selection[j]); ++right; continue; } if (selection[left + localCatchUp] >= arr[i]) { selection[left] = arr[i]; for (int j = left; selection[j] > selection[j + 1]; ++j) swap(selection[j], selection[j + 1]); --left; continue; } if (i & 1) { // i -  restFirst[restFirstLen++] = arr[i]; } else { restSecond[restSecondLen++] = arr[i]; } } 

फिर, यहाँ क्या हो रहा है? पहले हम तत्व को ऊँचाइयों तक पहुँचाने की कोशिश करते हैं। काम नहीं कर रहा है - अगर हो सके तो उसे चढ़ाव में फेंक दें। अगर यह भी करना असंभव है - इसे रेस्टफर्स्ट या रेस्टेकॉन्ड में डालें।

सबसे कठिन हिस्सा खत्म हो गया है। अब, लूप के बाद, हमारे पास एक चयन के साथ एक सॉर्ट किया गया सरणी है (तत्व इंडेक्स पर छोड़ते हैं [बाएं + 1] और अंत में [दाईं ओर - 1] ), साथ ही रेस्टफर्स्ट और रेस्टसेकंड एरे की लंबाई रेस्टफर्स्टलेन और रेस्टसेकॉन्डलीन, क्रमशः।

पिछले उदाहरण की तरह, पुनरावर्ती कॉल से पहले हम मेमोरी को मुख्य सरणी से मुक्त करते हैं (हमने पहले से ही इसके सभी तत्वों को सहेज लिया है)

 delete[] arr; 

हमारे चयन सरणी में अप्रयुक्त मेमोरी के कई सेल हो सकते हैं। एक पुनरावर्ती कॉल से पहले, आपको इसे मुक्त करने की आवश्यकता है।

अप्रयुक्त स्मृति को मुक्त करें

 int selectionLen = right - left - 1; //     int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); //        delete[] selection; //    2 * len   selection = copy; //      ,   

अब रिस्टोरस्ट और रेस्टसेकंड सरणियों के लिए हमारी तरह के फ़ंक्शन को पुनरावर्ती रूप से चलाएँ

यह समझने के लिए कि यह कैसे काम करता है, आपको सबसे पहले कोड को अंत तक देखना होगा। अभी के लिए, आपको बस यह विश्वास करने की आवश्यकता है कि पुनरावर्ती कॉल के बाद, रेस्ट फ़र्स्ट और रेस्टसेकंड सरणियों को सॉर्ट किया जाएगा।

 newGenerationSort(restFirst, restFirstLen); newGenerationSort(restSecond, restSecondLen); 

और अंत में, हमें परिणामी एक में 3 सरणियों को मर्ज करने और पॉइंटर अरेस्ट को असाइन करने की आवश्यकता है।

आप पहले restFirst + restSecond को कुछ restFull सरणी में मर्ज कर सकते हैं, और फिर चयन + restFull को मर्ज कर सकते हैं । लेकिन इस एल्गोरिथ्म में एक ऐसी संपत्ति है जिसमें सबसे अधिक संभावना है कि चयन सरणी में बाकी सरणियों की तुलना में बहुत कम तत्व होंगे। मान लें कि चयन में 100 तत्व हैं, restFirst में 990 हैं, और restSecond में 1010 शामिल हैं । फिर, एक RestFull सरणी बनाने के लिए, आपको 990 + 1010 = 2000 कॉपी संचालन करने की आवश्यकता है। फिर चयन के साथ विलय के लिए - एक और 2000 + 100 प्रतियां। इस दृष्टिकोण के साथ, कुल प्रति 2000 + 2100 = 4100 होगी।

चलो यहाँ अनुकूलन लागू करते हैं। पहले चयन को मर्ज करें और चयन सरणी में पुनर्स्थापित करें । कॉपी ऑपरेशन्स: 100 + 990 = 1090। इसके बाद, चयन और रेस्टेकंड ऐरे को मर्ज करें और एक और 1090 + 1010 = 2100 प्रतियां खर्च करें। कुल मिलाकर, 2100 + 1090 = 3190 जारी किया जाएगा, जो पिछले दृष्टिकोण के मुकाबले लगभग एक चौथाई कम है।

सरणियों का अंतिम विलय

 int* part2; int part2Len; if (selectionLen < restFirstLen) { glueDelete(selection, restFirst, restFirstLen, selection, selectionLen); // selection += restFirst selectionLen += restFirstLen; part2 = restSecond; part2Len = restSecondLen; } else { glueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); // part2 = restFirst + restSecond part2Len = restFirstLen + restSecondLen; } glueDelete(arr, selection, selectionLen, part2, part2Len); 

जैसा कि आप देख सकते हैं, अगर हमारे लिए रेस्टफर्स्ट के साथ चयन को मर्ज करना अधिक लाभदायक है, तो हम ऐसा करते हैं। अन्यथा, हम "restFull" के रूप में विलय कर देते हैं

 /// works only if arr is pointer assigned by new keyword void newGenerationSort(int*& arr, int len) { int localCatchUp = min(catchUp, len); //            insertionSort(arr, 0, localCatchUp - 1); //     localCatchUp  if (len <= localCatchUp) //       n <= catchUp  return; //      int* selection = new int[len << 1]; //     new int[len * 2] int left = len - 1; //       int right = len; //       selection[left--] = arr[0]; for (int i = 1; i < localCatchUp; ++i) { selection[right++] = arr[i]; } int restLen = len >> 1; int* restFirst = new int[restLen]; int* restSecond = new int[restLen]; int restFirstLen = 0; int restSecondLen = 0; for (int i = localCatchUp; i < len; ++i) { if (selection[right - localCatchUp] <= arr[i]) { selection[right] = arr[i]; for (int j = right; selection[j - 1] > selection[j]; --j) swap(selection[j - 1], selection[j]); ++right; continue; } if (selection[left + localCatchUp] >= arr[i]) { selection[left] = arr[i]; for (int j = left; selection[j] >= selection[j + 1]; ++j) swap(selection[j], selection[j + 1]); --left; continue; } if (i & 1) { // i -  restFirst[restFirstLen++] = arr[i]; } else { restSecond[restSecondLen++] = arr[i]; } } delete[] arr; int selectionLen = right - left - 1; //     int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); //        delete[] selection; //    2 * len   selection = copy; //      ,   newGenerationSort(restFirst, restFirstLen); newGenerationSort(restSecond, restSecondLen); int* part2; int part2Len; if (selectionLen < restFirstLen) { glueDelete(selection, restFirst, restFirstLen, selection, selectionLen); // selection += restFirst selectionLen += restFirstLen; part2 = restSecond; part2Len = restSecondLen; } else { glueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); // part2 = restFirst + restSecond part2Len = restFirstLen + restSecondLen; } glueDelete(arr, selection, selectionLen, part2, part2Len); } 

अब समय परीक्षण

 #include <iostream> #include <ctime> #include <vector> #include <algorithm> #include "time_utilities.h" #include "sort_utilities.h" using namespace std; using namespace rela589n; void printArr(int* arr, int len) { for (int i = 0; i < len; ++i) { cout << arr[i] << " "; } cout << endl; } bool arraysEqual(int* arr1, int* arr2, int len) { for (int i = 0; i < len; ++i) { if (arr1[i] != arr2[i]) { return false; } } return true; } int* createArray(int length) { int* a1 = new int[length]; for (int i = 0; i < length; i++) { a1[i] = rand(); //a1[i] = (i + 1) % (length / 4); } return a1; } int* array_copy(int* arr, int length) { int* a2 = new int[length]; for (int i = 0; i < length; i++) { a2[i] = arr[i]; } return a2; } void tester(int tests, int length) { double t1, t2; int** arrays1 = new int* [tests]; int** arrays2 = new int* [tests]; for (int t = 0; t < tests; ++t) { //    int* arr1 = createArray(length); arrays1[t] = arr1; arrays2[t] = array_copy(arr1, length); } t1 = getCPUTime(); for (int t = 0; t < tests; ++t) { quickSort(arrays1[t], 0, length - 1); } t2 = getCPUTime(); cout << "Avg Qsort time for " << length << " elements: " << (t2 - t1) * 1000 / tests << endl; int portion = catchUp = 8; t1 = getCPUTime(); for (int t = 0; t < tests; ++t) { newGenerationSort(arrays2[t], length); } t2 = getCPUTime(); cout << "Avg newGenSort time for " << length << " elements: " << (t2 - t1) * 1000 / tests //<< " Catch up coef: "<< portion << endl; bool confirmed = true; //     for (int t = 0; t < tests; ++t) { if (!arraysEqual(arrays1[t], arrays2[t], length)) { confirmed = false; break; } } if (confirmed) { cout << "Confirmed" << endl; } else { cout << "Review your code! Something wrong..." << endl; } } int main() { srand(time(NULL)); int length; double t1, t2; cout << "size: "; cin >> length; int t; cout << "tests: "; cin >> t; tester(t, length); system("pause"); return 0; } 

 // [min, max] int random(int min, int max) { return min + rand() % ((max + 1) - min); } void quickSort(int * arr, int b, int e) { int l = b, r = e; int piv = arr[random(l, r)]; while (l <= r) { for (; arr[l] < piv; ++l); for (; arr[r] > piv; --r); if (l <= r) swap(arr[l++], arr[r--]); } if (b < r) quickSort(arr, b, r); if (e > l) quickSort(arr, l, e); } 

 #pragma once #if defined(_WIN32) #include <Windows.h> #elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__)) #include <unistd.h> #include <sys/resource.h> #include <sys/times.h> #include <time.h> #else #error "Unable to define getCPUTime( ) for an unknown OS." #endif /** * Returns the amount of CPU time used by the current process, * in seconds, or -1.0 if an error occurred. */ double getCPUTime() { #if defined(_WIN32) /* Windows -------------------------------------------------- */ FILETIME createTime; FILETIME exitTime; FILETIME kernelTime; FILETIME userTime; if (GetProcessTimes(GetCurrentProcess(), &create;Time, &exit;Time, &kernel;Time, &user;Time) != -1) { SYSTEMTIME userSystemTime; if (FileTimeToSystemTime(&user;Time, &user;SystemTime) != -1) return (double)userSystemTime.wHour * 3600.0 + (double)userSystemTime.wMinute * 60.0 + (double)userSystemTime.wSecond + (double)userSystemTime.wMilliseconds / 1000.0; } #elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__)) /* AIX, BSD, Cygwin, HP-UX, Linux, OSX, and Solaris --------- */ #if defined(_POSIX_TIMERS) && (_POSIX_TIMERS > 0) /* Prefer high-res POSIX timers, when available. */ { clockid_t id; struct timespec ts; #if _POSIX_CPUTIME > 0 /* Clock ids vary by OS. Query the id, if possible. */ if (clock_getcpuclockid(0, &id;) == -1) #endif #if defined(CLOCK_PROCESS_CPUTIME_ID) /* Use known clock id for AIX, Linux, or Solaris. */ id = CLOCK_PROCESS_CPUTIME_ID; #elif defined(CLOCK_VIRTUAL) /* Use known clock id for BSD or HP-UX. */ id = CLOCK_VIRTUAL; #else id = (clockid_t)-1; #endif if (id != (clockid_t)-1 && clock_gettime(id, &ts;) != -1) return (double)ts.tv_sec + (double)ts.tv_nsec / 1000000000.0; } #endif #if defined(RUSAGE_SELF) { struct rusage rusage; if (getrusage(RUSAGE_SELF, &rusage;) != -1) return (double)rusage.ru_utime.tv_sec + (double)rusage.ru_utime.tv_usec / 1000000.0; } #endif #if defined(_SC_CLK_TCK) { const double ticks = (double)sysconf(_SC_CLK_TCK); struct tms tms; if (times(&tms;) != (clock_t)-1) return (double)tms.tms_utime / ticks; } #endif #if defined(CLOCKS_PER_SEC) { clock_t cl = clock(); if (cl != (clock_t)-1) return (double)cl / (double)CLOCKS_PER_SEC; } #endif #endif return -1; /* Failed. */ } 

मशीन पर सभी परीक्षण एक प्रतिशत पर किए गए थे। इंटेल कोर i3 7100u और 8GB रैम

पूरी तरह से यादृच्छिक सरणी

 a1[i] = rand(); 

आंशिक रूप से आदेशित ऐरे

 a1[i] = (i + 1) % (length / 4); 

पूरी तरह से सॉर्ट किया गया ऐरे

 a1[i] = (i + 1); 

निष्कर्ष

जैसा कि आप देख सकते हैं, एल्गोरिथ्म काम करता है और अच्छी तरह से काम करता है। कम से कम हम जो चाहते थे वह सब हासिल हो गया। स्थिरता की कीमत पर, मुझे यकीन नहीं है कि मैंने जांच नहीं की है। आप इसे स्वयं देख सकते हैं। लेकिन सिद्धांत रूप में इसे बहुत आसानी से हासिल किया जाना चाहिए। बस कुछ स्थानों में,> साइन के बजाय, something या कुछ और डालें।