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

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

पढ़ने से पहले, मैं सुझाव देता हूं कि आप उपयोगकर्ता वेलेमाक द्वारा लेख पढ़ें:

→ एक्सचेंज सॉर्टिंग
→ बबल सॉर्ट और ऑल-ऑल-ऑल
→ मूर्खतापूर्ण सॉर्ट और कुछ अन्य स्मार्ट

बबल सॉर्ट

सबसे आसान विकल्प पहले तत्व से आखिरी तक सरणी पर ओवररेट करना है, इंटरचेंजिंग (यदि आवश्यक हो) पड़ोसी तत्व।

→ यहाँ देखें


स्लाइडर को स्थानांतरित करने के लिए, आपको निचले बाएं कोने में ग्रे बटन पर क्लिक करना होगा।
जब आप बटन पर क्लिक करते हैं, तो स्लाइडर को दाईं ओर ले जाएं

slider++; 

अगला, हम जांचते हैं: क्या हम सरणी के अंत में पहुंच गए हैं (फिर शुरुआत में कूदें), फिर पड़ोसी तत्वों की तुलना करें (इंटरचेंज)


प्रसंस्करण .js जावा डेटा संरचनाओं का उपयोग करता है, फिर कोड को जावास्क्रिप्ट ( लिंक ) में अनुवादित किया जाता है, इसलिए मॉड्यूल वर्ग के उदाहरणों की एक सरणी की घोषणा, जो तत्वों को प्रस्तुत करने और उदाहरणों को शुरू करने के लिए जिम्मेदार है, ऐसा होता है

ड्राइंग ड्रॉ () ड्राइंग का मुख्य कार्य एक अनंत लूप है जिसमें क्लास इंस्टेंसेस को सॉर्ट किया जाता है

 for (Module mod : mods) { mod.display(); } 

रैंडफू () फ़ंक्शन जोड़ें, जो यादृच्छिक मान लौटाता है। यह सुनिश्चित करने के लिए कि मान दोहराए नहीं जाते हैं, हम उन्हें सूची सूची में ArrayLis t, और randFoo () फ़ंक्शन में जोड़ देंगे , यह देखने के लिए जांचें कि क्या नया यादृच्छिक संख्या सूची में है या नहीं

 int randFoo(){ newRand = int(random(1,11)); if(!listRand.contains(newRand) ) listRand.add(newRand ); else newRand=randFoo(); return newRand; } 

→ यहाँ देखें

पिक्सेल क्रमबद्ध

पिक्सेल छँटाई (यहाँ) बुलबुला छँटाई का एक कार्यान्वयन है।
हम वार्मर / लाइटर पिक्सल्स को एक तरफ शिफ्ट करेंगे, और गहरा / ठंडा करने वालों को दूसरी तरफ

 void draw(){ while (i <= height) { c=get(i,j); //    cTemp=c; //      i++; //     c=get(i,j); //     if(cTemp>c) { //   fill(c); //    rect(i-1,j,1,1); fill(cTemp); rect(i,j,1,1); } } if(mousePressed) { if(j>=width) j=0; } //      if(i >= height) {j++; i=0;} } 

→ यहाँ देखें
सॉर्टिंग शुरू करने के लिए, चित्र पर क्लिक करें और बटन दबाए रखें।
आप यहाँ पिक्सेल प्रकारों के बारे में अधिक पढ़ सकते हैं।
आधिकारिक चैनल द कोडिंग ट्रेन पर पिक्सेल छँटाई के बारे में वीडियो यहाँ

सीमक और झंडा

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

 if(slider>=limiter) { slider=1; limiter--; if(limiter<1) limiter=1; } 

→ यहाँ देखें

बस्ट की संख्या को कम करने का एक अन्य तरीका आलेख बबल सॉर्ट (विकिपीडिया) में पाया जा सकता है। यदि सरणी के पारित होने के दौरान हमने कभी भी पड़ोसी तत्वों को स्विच नहीं किया है, तो सरणी को क्रमबद्ध किया जाता है और चक्र पूरा किया जा सकता है ( आइवरसन )।

एक ध्वज ध्वज जोड़ें, जो तब उठाया जाता है जब हम कुछ ऐसे तत्वों से मिलते हैं, जिन्हें परस्पर जुड़ने की आवश्यकता होती है। यदि ध्वज उठाया गया है, तो पुन: सरणी पर पुन: व्यवस्थित करें। यदि नहीं, तो चक्र समाप्त करें। ध्वज की स्थिति कंसोल में प्रदर्शित होती है।



→ यहाँ देखें

यदि आप बाईं ओर एक सीमक लगाते हैं और संदर्भ / न्यूनतम के रूप में एक सीमक के साथ एक तत्व का उपयोग करते हैं, तो हम चयन द्वारा छंटनी करते हैं।

न्यूनतम मूल्य लोड किया जाएगा, जिसमें न्यूनतम करने के लिए मिनट चर जोड़ें। मान लीजिए कि शुरू में सबसे बाईं ओर का तत्व न्यूनतम है: सरणी के पहले पास के दौरान, यदि कोई तत्व न्यूनतम से कम है, तो हम इस तत्व को चर मिनट में ही सहेजते हैं

 if(mods[slider-1].rectHight < min){ min=mods[slider-1].rectHight; } 

फिर पहले तत्व और न्यूनतम स्वैप करें

 if (mods[limiterL-1].rectHight>min) { vTemp= mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[slider-1].rectHight; mods[slider-1].rectHight=vTemp; } 

यदि स्लाइडर सरणी के दाहिने किनारे तक पहुँचता है, तो सीमक एक कदम दाईं ओर जाता है, और स्लाइडर सीमक की ओर बढ़ता है

 if(slider==moduleSize){ if(limiterL<moduleSize) limiterL++; min=mods[limiterL-1].rectHight; incPaddle=limiterL-1; } 

→ यहाँ देखें
उपायों की संख्या को कम किया जा सकता है यदि खोज की शुरुआत में हम वर्तमान तत्व और सरणी के सबसे सही तत्व की तुलना (इंटरचेंज) करते हैं।

 if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight) { vTemp=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight; mods[moduleSize-1].rectHight=vTemp; } 

फिर आप सरणी के सबसे सही तत्व की जांच नहीं कर सकते

 //if(slider==moduleSize){ if(slider==moduleSize-1){ //if(limiterL<moduleSize) limiterL++; limiterL++; min=mods[limiterL-1].rectHight; slider=limiterL-1; } // slider++; if(slider<moduleSize) slider++; 

→ यहाँ देखें

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

त्वरित छाँट

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

बौना क्रमबद्ध

अनिवार्य रूप से, सूक्ति अगले और पिछले बगीचे के बर्तनों को देखती है: यदि वे सही क्रम में हैं, तो वह एक पॉट आगे बढ़ाता है, अन्यथा वह उन्हें स्वैप करता है और एक पॉट वापस करता है।

ध्वज को उठाने के बाद, स्लाइडर को वेरिएबल लिमिटर में समन्वयित करें और स्लाइडर को चरणों में सरणी की शुरुआत में लौटा दें।

 slider--; 

एक बार सरणी की शुरुआत में, ध्वज को रीसेट करें और स्लाइडर को उस समन्वय के साथ सेल में डालें जिसे हमने चर सीमक में बचाया था

 if(slider==0){ flag=false; slider=limiterR; } 

→ यहाँ देखें

इस एल्गोरिथ्म को बदलकर, हम " आवेषण द्वारा छँटाई " करते हैं।
आवेषण द्वारा छंटनी में, संदर्भ / न्यूनतम तत्व का चयन किया जाता है, फिर सरणी के अनसोल्ड भाग में, तत्व का चयन किया जाता है, संदर्भ से छोटा और संदर्भ से पहले डाला जाता है

हमारे पास पिछले वाले के साथ न्यूनतम तत्व विनिमय स्थान हैं, संदर्भ एक तक, और इसी तरह। संदर्भ के सामने डाला गया।
एक शर्त जोड़ें

 if(slider==limiterR-1 && mods[slider-1].rectHight<mods[limiterR-1].rectHight){ flag=false; slider=limiterR; } 

→ यहाँ देखें


"त्वरित" सम्मिलन छँटाई

इस एल्गोरिथ्म में, सहायक तत्व द्वारा सरणी को दो भागों में विभाजित किया गया है।
पहले तत्व को संदर्भ दें: तुलना करें, दूसरे से शुरू, संदर्भ के साथ सरणी के तत्व, यदि कोई तत्व संदर्भ से छोटा है

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight) 

संदर्भ से पहले पाया गया तत्व डालें

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight){ flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; } 

यदि ध्वज उठाया गया है, तो स्लाइडर को बाईं ओर ले जाएं जब तक कि हम समर्थन तत्व को पूरा नहीं करते

 if(flag){ slider--; if(slider<pivot){ flag=false; //   pivot++; slider=pivot; } } 

इस प्रकार सरणी को दो भागों में विभाजित किया गया है, बाईं ओर - तत्व संदर्भ से छोटे हैं, दाईं ओर - अधिक

→ यहाँ देखें

यदि, प्रत्येक गणना के बाद, समर्थन तत्व के निर्देशांक ext में सहेजे जाते हैं। pivotsArr सरणी, तब जब संदर्भ तत्व दाहिने किनारे पर पहुंचता है, तो हमें स्तर / चरण द्वारा क्रमबद्ध एक सरणी मिलती है। प्रत्येक अगले स्तर के तत्व पिछले स्तर के तत्वों से बड़े होंगे। स्तरों की सीमाएं ऐड में निहित होंगी। pivotsArr सरणी
जितनी बार आप बटन पर क्लिक करेंगे, हम कंसोल में pivotsArr एरे को आउटपुट करेंगे

 for(int i=0;i<pivotsArr.length;i++){ print(" "); print(pivotsArr[i]); print(" "); } 

प्रोग्राम के अंत में यादृच्छिक फ़ंक्शन रैंडफू () जोड़ें।

→ यहाँ देखें

अब आपको प्रत्येक स्तर के तत्वों को अलग-अलग क्रमबद्ध करना होगा (यह केवल चक्र को समाप्त करने के लिए स्थिति जोड़ने के लिए रहता है)

→ यहाँ देखें
इस छँटाई को स्तर द्वारा छँटाई के रूप में वर्णित किया जा सकता है।
, क्योंकि प्रत्येक गणना के बाद, संख्यात्मक डेटा को स्तरों में व्यवस्थित किया जाता है, प्रत्येक अगले स्तर की संख्या पिछले एक में संख्याओं से अधिक होती है।

अजीब-सी छँटाई भी

हम पड़ोसी तत्वों की तुलना करते हुए स्लाइडर को दो चरणों में स्थानांतरित करेंगे

 slider=slider+2; 

इस प्रकार हम 0 और 1, 2 और 3, 4 और 5, 6 और 7, आदि तत्वों की तुलना करते हैं।
यदि स्लाइडर सरणी के किनारे तक पहुंच जाता है, तो सीमक को एक कदम बाईं ओर ले जाएं, और स्लाइडर सरणी की शुरुआत में चले जाएं।
अगला, हम तत्वों 1 और 2, 3 और 4, 5 और 6, 7 और 8, आदि की तुलना करते हैं।
सीमक तक पहुंचने के बाद, हम इसे दाईं ओर एक कदम आगे बढ़ाते हैं, सरणी की शुरुआत में स्लाइडर डालते हैं।

→ यहाँ देखें

हेयरब्रश को क्रमबद्ध करें

स्लाइडर को सरणी की शुरुआत में और दाईं ओर दाईं ओर स्थित होने दें। (स्वैप) तत्वों की तुलना करें। हम सीमक को एक कदम बाईं ओर ले जाते हैं और इसके इंडेक्स को लिमिटरस्टोर चर में सहेजते हैं

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

चरणों में सरणी के अंत तक स्टॉप के साथ स्लाइडर को स्थानांतरित करें

 if(limiter!=moduleSize) { //  limiter     limiter++; slider++; } 

एक सीमक के रूप में सरणी के अंत तक पहुंचने के बाद, सरणी की शुरुआत में स्लाइडर डालें, और सीमक को सीमक -१ में रखें।

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

→ यहाँ देखें

शेकर तरह

सरणी की शुरुआत में बायां सीमक सीमक जोड़ें।
फ़्लैग फ़्लैग को बढ़ने दें जब स्लाइडर दाहिने सीमक सीमक तक पहुँचता है, तो सीमांकक एक कदम बाईं ओर चलता है। इसके अलावा, जब झंडा उठाया जाता है, स्लाइडर बाएं सीमक सीमक पर वापस कदम रखता है - सीमक एक कदम दाईं ओर जाता है - स्लाइडर दाईं ओर के चरणों में चला जाता है


→ यहाँ देखें

पसंद के अनुसार शेकर
दाहिने सीमक के साथ बबल लिमिटर के साथ बबल सॉर्ट में जोड़ें। स्लाइडर के दाईं ओर प्रत्येक शिफ्ट में, हम जांच (स्वैप) करते हैं, जो कि अधिक है - वर्तमान तत्व या सीमक

 if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=vTemp; } 

जब स्लाइडर दाईं सीमा सीमक तक पहुँच जाता है, तो दाहिने सीमक बाएँ से एक कदम चलता है, बायाँ सिरा दाईं ओर एक कदम बढ़ता है, स्लाइडर बाएँ लिमिटर में लौटता है

 if(slider>=limiterR){ limiterL++; slider=limiterL; limiterR--; } 

→ यहाँ देखें

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