एल्गोरिदम की दुनिया में: सॉर्ट डालें

लेखक से
यह लेख एक ऐरे के लिए एल्गोरिदम पर विचार करता है। यह शुरुआती लोगों के लिए या उन लोगों के लिए है जो किसी कारण से इस एल्गोरिथम से परिचित नहीं हैं। सुधार और सुधार केवल स्वागत है :)

सिद्धांत
सम्मिलन सॉर्ट एक सरल सॉर्टिंग एल्गोरिथ्म है। इसका सार इस तथ्य में निहित है कि, एल्गोरिथ्म के प्रत्येक चरण में, हम सरणी के तत्वों में से एक लेते हैं, सम्मिलित करने और सम्मिलित करने की स्थिति का पता लगाते हैं। यह ध्यान देने योग्य है कि 1 तत्व की एक सरणी को क्रमबद्ध माना जाता है।

एल्गोरिथ्म का मौखिक विवरण जटिल लगता है, लेकिन वास्तव में यह लागू करने के लिए सबसे आसान छँटाई है। हम में से प्रत्येक, गतिविधि के प्रकार की परवाह किए बिना, छंटाई एल्गोरिथ्म का उपयोग करता था, बस इसका एहसास नहीं था :) उदाहरण के लिए, जब बटुए में नोटों की छंटाई करते हैं - हम 100 रूबल लेते हैं और देखो - 10, 50 और 500 रूबल बैंक नोट हैं। यह सिर्फ ५० से ५०० के बीच है और हम अपने सौ को सम्मिलित कर रहे हैं :) या मैं सभी पुस्तकों से एक उदाहरण दूंगा - कार्ड "मल" खेल रहा हूं। जब हम डेक से एक कार्ड खींचते हैं, तो हम अपने कार्ड को आरोही क्रम में व्यवस्थित करते हुए देखते हैं, और खींचे गए कार्ड के मूल्य के आधार पर, कार्ड को उचित स्थान पर रखते हैं। स्पष्टता के लिए, मैं विकिपीडिया से एक एनीमेशन दूंगा।


कार्यान्वयन
कार्यान्वयन के साथ आगे बढ़ने से पहले, हम इनपुट डेटा के प्रारूप को निर्धारित करेंगे - उदाहरण के लिए, यह पूर्णांक (इंट) मानों की एक सरणी होगी। सरणी के तत्वों की संख्या 0 से शुरू होती है और n-1 के साथ समाप्त होती है। एल्गोरिथ्म स्वयं C ++ में लागू किया गया है। तो चलिए शुरू करते हैं ...
एल्गोरिथ्म का मुख्य लूप 0 वें तत्व से शुरू नहीं होता है, लेकिन 1 से, क्योंकि 1 तत्व तक का तत्व हमारा क्रमबद्ध अनुक्रम होगा (याद रखें कि एक तत्व की एक सरणी को सॉर्ट किया गया है) और हम पहले से ही इस तत्व के सापेक्ष संख्या 0 से सम्मिलित करेंगे। बाकी सब। वास्तव में कोड:

for(int i=1;i<n;i++) for(int j=i;j>0 && x[j-1]>x[j];j--) //  j>0   j-1 > j, x- int swap(x[j-1],x[j]); //    j  j-1 

छंटनी कार्यान्वयन बहुत सरल है, केवल 3 लाइनें। स्वैप फ़ंक्शन तत्व x [j-1] और x [j] को स्वैप करता है। एक नेस्टेड लूप डालने के लिए जगह की तलाश में है। मैं इस एल्गोरिथम को याद रखने की सलाह देता हूं ताकि यदि आवश्यक हो, तो छंटाई लिखें ताकि बुलबुले द्वारा छंटाई न हो सके :)

प्रदर्शन विश्लेषण
सम्मिलन सॉर्टिंग में जटिलता n ^{2 है} , तुलना की संख्या सूत्र n * (n-1) / 2 का उपयोग करके गणना की जाती है। प्रमाण के लिए, निम्नलिखित कोड लिखा गया था:

 void Sort(int* arr,int n){ int counter=0; for(int i=1;i<n;i++){ for(int j=i; j>0 && arr[j-1]>arr[j];j--){ counter++; int tmp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=tmp; } } cout<<counter<<endl; } 

100 तत्वों के लिए क्रमपरिवर्तन की संख्या:

इसलिए, n = 100 के साथ, क्रमपरिवर्तन की संख्या 4950 है, और 10000 नहीं यदि हमने सूत्र n ² का उपयोग करके गणना की। एक छँटाई एल्गोरिथ्म चुनते समय इसे ध्यान में रखें।

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