और हम सभी स्मार्ट और कुशल एल्गोरिदम क्या हैं? और चलो इस नशे की शरद ऋतु शुक्रवार को कुछ प्रतिफल के साथ दूर कर दें!

मैं आपका ध्यान अब तक के सबसे अपरंपरागत सॉर्टिंग के TOP-5 पर देता हूं।

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

दलदल सॉर्ट (BogoSort)

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

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

औसत समय जटिलता: O (nxn!)। एक बेहतर भी है: Ω (एन)। दिलचस्प है, इस एल्गोरिथ्म की सबसे खराब अस्थायी जटिलता विज्ञान के लिए अज्ञात है।

धीरे। में फंस जाने का कोड।

import java.util.Random; public class BogoSortAlgorithm extends SortAlgorithm { //  ,     public void sort(int data[]) throws Exception { if (data.length > 0) runBogoSort(data); } //     private void runBogoSort(int data[]) throws Exception { Random generator; int tempVariable; int randomPosition; do { generator = new Random(); for (int i = 0; i < data.length; i++) { randomPosition = generator.nextInt(data.length); tempVariable = data[i]; data[i] = data[randomPosition]; data[randomPosition] = tempVariable; pause(i,randomPosition); } } while(!isSorted(data)); //   } //,    private boolean isSorted(int data[]) { for (int i = 1; i < data.length; i++) if (data[i] < data[i - 1]) return false; return true; } }

Bozo जोकर सॉर्ट (BozoSort)

जहाँ BogoSort है, वहाँ BozoSort है। Bozo baby मसख़री छँटाई विधि तीन साल के बच्चे के लिए भी समझाना आसान है। हम बेतरतीब ढंग से दो तत्वों का चयन करते हैं, उन्हें स्वैप करते हैं, और यह देखने के लिए जांचें कि क्या इससे सफलता मिली है। यदि नहीं, तो हम उसी क्रिया को दोहराते हैं - और इसी तरह अंत तक।

ऐसा लग सकता है कि BozoSort BogoSort के समान है, लेकिन यह केवल पहली नज़र में है। ओ (nxn!) के एक औसत समय जटिलता के साथ क्लाउन बूज़ो सॉर्ट और यह ऊपरी समय सीमा भी है।

युपीडी। जैसा कि burdakovd और SkidanovAlex ने टिप्पणियों और निजी संदेशों में सही बताया है , बोगोॉर्ट की तरह, बोजो के जोकर को छांटना, सबसे खराब समय जटिलता के लिए कोई ऊपरी सीमा नहीं है। वास्तव में, यह कहां से आता है, अगर सबसे खराब स्थिति में, एक अनसुलझी सरणी में, यादृच्छिक हमेशा एक ही दो तत्वों को इंटरचेंज करेगा!

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

क्लाउन बोजो भी शानदार प्रोग्रामिंग है।

 import java.util.Random; class BozoSortAlgorithm extends SortAlgorithm { void sort(int a[]) throws Exception { boolean sorted = false; //    while (!sorted) { //    ... int index1 = Randomize(a.length); int index2 = Randomize(a.length); //...     int temp = a[index2]; a[index2] = a[index1]; a[index1] = temp; pause(index1, index2); //? sorted = true; for (int i = 1; i < a.length; i++) { if (a[i-1] > a[i]) { pause(i, i-1); sorted = false; break; } } } } //     private int Randomize( int range ) { double rawResult; rawResult = Math.random(); return (int) (rawResult * range); } }

क्रमपरिवर्तन क्रमबद्ध (PermSort)

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

बोझा मसखरा की तरह सबसे खराब समय कठिनाई ओ (एन एक्स एन!) है। लेकिन सबसे अच्छी चीजों के साथ बेहतर है - ओ (एन)।

किसी सरणी के सभी क्रमपरिवर्तन की सुरुचिपूर्ण गणना।

 class PermSortAlgorithm extends SortAlgorithm { // ? boolean issorted(int a[], int i) throws Exception { for (int j = a.length-1; j > 0; j--) { //    -  compex(j, j - 1); if(a[j] < a[j - 1]) { return false; } } return true; } // PermSort boolean sort(int a[], int i) throws Exception { int j; //     if (issorted(a, i)) { return true; } //   . //    . for(j = i+1; j < a.length; j++) { compex(i, j); //-  int T = a[i]; a[i] = a[j]; a[j] = T; //    if(sort(a, i + 1)) { return true; } //    T = a[i]; a[i] = a[j]; a[j] = T; } return false; } //      PermSort. void sort(int a[]) throws Exception { sort(a, 0); } }

सिली सॉर्ट (स्टॉग सॉर्ट)

सॉर्टिंग का नाम कॉमिक ट्रूप थ्री स्टोग्स के नाम पर रखा गया है, जो पिछली शताब्दी में अमेरिकी जनता को खुश करता था: 1930 के दशक की शुरुआत से 1960 के दशक के अंत तक। वैसे, कुल छह "बेवकूफ" थे, रचनात्मक गतिविधियों के 4 दशकों में, तीनों की रचना कभी-कभी बदल जाती थी।

जॉली ट्रिनिटी फ़ार्स और क्लाउनिंग में विशेष। छंटनी भी व्यवहार करती है: एक कैरिकेचर चरित्र की तरह, वह एक सरणी में पागल हो जाती है; जैसा कि यह बफूनरी में होना चाहिए - मुख्य चरित्र के साथ हास्यास्पद रोमांच के बाद, सब कुछ ठीक है। ऐरे छांटे, खुश अंत।

एल्गोरिथ्म मजाकिया पुनरावर्ती है।

 class StoogeSortAlgorithm extends SortAlgorithm { void sort(int a[], int lo, int hi) throws Exception { ///     if(a[lo] > a[hi]) { int T = a[lo]; a[lo] = a[hi]; a[hi] = T; } // ? if(lo + 1 >= hi) return; //   ? int third = (hi - lo + 1) / 3; sort(a, lo, hi - third); //  2/3  sort(a, lo + third, hi); //  2/3  sort(a, lo, hi - third); //  2/3  } //     void sort(int a[]) throws Exception { sort(a, 0, a.length-1); } }

हम सरणी का एक खंड लेते हैं (पहले यह पूरे सरणी है) और खंड के अंत में तत्वों की तुलना करें। यदि बाएं दाएं से बड़ा है, तो, निश्चित रूप से, हम स्थानों को स्वैप करते हैं।
फिर, यदि किसी खंड में कम से कम तीन तत्व हैं, तो:
1) खंड के पहले 2/3 के लिए स्टोगो सॉर्ट को कॉल करें;
2) खंड के अंतिम 2/3 के लिए Stooge सॉर्ट करें;
3) खंड के पहले 2/3 के लिए फिर से Stooge सॉर्ट करें।

एल्गोरिथ्म की जटिलता प्रभावशाली रूप से गणना की जाती है: ओ (एन ^{लॉग 3 / लॉग 1.5} )। ये कुछ मैला ओ (n) नहीं हैं।

छँटाई बाबुशकिना (बाबुश्किन सॉर्ट)

बाबूसकिन स्वयं सीधे विधि के लेखक नहीं हैं, हालांकि यह एलेक्सी के गहरे विचार थे जिन्होंने एल्गोरिथ्म का आधार बनाया था।

दादी के बारे में संक्षिप्त जानकारी

अर्नई बाबुश्किन, एक प्रोग्रामर जो बरनौल से है, उद्यमी, इनोवेटर। अल्ताई राज्य तकनीकी विश्वविद्यालय के 4 वर्षीय छात्र।

गिने-चुने स्कूली बच्चों और नौजवानों के लिए क्षेत्रीय शैक्षिक कार्यक्रम में भाग लेने वाले "भविष्य का अल्ताई"। विज्ञान प्रतियोगिता में स्टार्ट का विजेता।

वैज्ञानिक और तकनीकी क्षेत्र में छोटे उद्यमों के विकास को बढ़ावा देने के लिए फंड द्वारा संचालित कार्यक्रम "U.M.N.I.K."।

पेटेंट किए गए एंटीवायरस इम्युनिटी के डेवलपर। मूल फ्लैश मार्कर गैजेट के निर्माता। फ़ाइलों को संग्रह करने के लिए एक मौलिक नए एल्गोरिथ्म के लेखक।

Microsoft के निमंत्रण पर, वह सीधे विंडोज 8 के बीटा संस्करण के परीक्षण में शामिल था।

एक बुनियादी रूप से नई फ़ाइल संग्रह एल्गोरिथ्म Babushkin द्वारा प्रस्तावित

संग्रह एल्गोरिथ्म निम्नानुसार है: कोई भी फ़ाइल वर्णों का एक HEX अनुक्रम है, इस HEX को DEC में अनुवादित करें, एक गैर-घातक बड़ी संख्या प्राप्त करें, इससे पहले 0 नंबर को जोड़ दें, हमें 0 से 1 तक की श्रेणी में दशमलव स्थानों की एक बड़ी संख्या के साथ नंबर मिलता है, और फिर सब कुछ बस - हम 2 ऐसे पूर्णांक संख्याओं का चयन करते हैं, जिनमें से भागफल हमें 0 से 1 तक सीमा में वांछित संख्या को मैचों की सटीकता के साथ अंतिम चरित्र तक पहुंचाएगा। परेशानी संख्या के चयन में है, जो 2 घंटे तक जा सकती है, और 2 सप्ताह तक जा सकती है। प्रोटोटाइप और एक काम कर रहे कार्यक्रम हैं, और यह सब काम करता है।

एलेक्सी बाबुश्किन

N तत्वों की एक सरणी दें। उनके स्थानों में तत्वों के विस्थापन के अनुक्रम को एन-रिक एकल-अंकों की संख्या की एक श्रृंखला के रूप में दर्शाया जा सकता है। इस अनुक्रम को एक बहु-अंकों वाला n-ric नंबर माना जा सकता है (हम इसे बाबुश्किन की संख्या कहते हैं)। इस संख्या का प्रत्येक बिट सरणी की स्थिति का एक सूचकांक है जिसमें अगला तत्व सम्मिलित करना है। इतनी संख्या कैसे प्राप्त करें? यदि हम 10-दशमलव रूप में दादी की संख्या का प्रतिनिधित्व करते हैं, तो हमें एक बड़ी (या बहुत नहीं, सरणी के आकार पर निर्भर करता है) संख्या मिलती है, इससे पहले 0 नंबर जोड़ें, हमें एक निश्चित संख्या में दशमलव स्थानों के साथ, 0 से 1 तक की सीमा में एक आंशिक संख्या मिलती है, और फिर यह सरल है - हम 2 ऐसे पूर्णांक संख्याओं का चयन करते हैं, जिनमें से भागफल हमें 0 से 1 तक की सीमा में वांछित संख्या के साथ मैचों की सटीकता के साथ अंतिम चरित्र तक पहुंचाएगा। हमें 2 भागफल संख्याएँ मिलती हैं, जो बाबूसकिन की संख्या बताती हैं - हमें स्वचालित रूप से क्रमपरिवर्तन का एक क्रम मिलता है जो सरणी को आदेश देता है।

किसी को कुछ स्पष्ट नहीं है? बाबूसकिना को चरण दर चरण छाँटना:

1) मान लीजिए कि आप n तत्वों की एक सारणी को क्रमबद्ध करना चाहते हैं (अनुक्रमण 0 से शुरू होता है, अंतिम तत्व का सूचकांक n - 1 है)।
2) हम दो परस्पर सरल दशमलव संख्याओं का चयन करते हैं, x और y (x <y)।
3) x को y से विभाजित करें। हमें 0 से 1 तक एक भिन्नात्मक संख्या मिलती है। हम शून्य को छोड़ देते हैं, भिन्नात्मक भाग को छोड़ देते हैं। वास्तव में, हमें एक निश्चित दशमलव पूर्णांक मिलता है।
4) चरण 3 में प्राप्त संख्या का DEC प्रतिनिधित्व n- दशमलव संख्या प्रणाली में अनुवादित है।
5) हम सरणी में 0 तत्व लेते हैं और इसे एक अतिरिक्त सरणी में उस स्थिति में रखते हैं जिसका सूचकांक चरण 4 में प्राप्त संख्या के एन-दशमलव प्रतिनिधित्व में पहले अंक के बराबर है।
6) हम सरणी में 1 तत्व लेते हैं और इसे एक अतिरिक्त सरणी में उस स्थिति में रखते हैं जिसका सूचकांक चरण 4 में प्राप्त संख्या के एन-दशमलव प्रतिनिधित्व में दूसरे अंक के बराबर है।
7) हम 2 तत्व को सरणी में लेते हैं और इसे एक अतिरिक्त सरणी में उस स्थिति में रखते हैं जिसका सूचकांक चरण 4 में प्राप्त संख्या के एन-दशमलव प्रतिनिधित्व में तीसरे अंक के बराबर है।
...
n + 3) हम सरणी में (n - 2) वें तत्व को लेते हैं और इसे एक अतिरिक्त सरणी में उस स्थिति में रखते हैं जिसका सूचकांक चरण 4 में प्राप्त संख्या के n- दशमलव प्रतिनिधित्व में पारंगत अंक है।
n + 4) सरणी में (n - 1) वें तत्व को लीजिए और इसे एक अतिरिक्त सरणी में उस स्थिति में रखिए जिसका सूचकांक चरण 4 में प्राप्त संख्या के n- दशमलव प्रतिनिधित्व में अंतिम अंक के बराबर हो।
n + 5) हम अतिरिक्त एरे से सभी तत्वों को मुख्य एक में स्थानांतरित करते हैं।
n + 6) लाभ !!!

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

प्रोटोटाइप और एक काम कर रहे कार्यक्रम हैं और यह सब काम करता है।

जावा में दादी की छँटाई।

दुर्भाग्य से, दादी की छँटाई का जावा कार्यान्वयन नहीं पाया जा सका। माफ़ कीजिए।

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

विशेष रूप से जावा उदाहरण प्रदान करने के लिए पैट्रिक मोरिन का विशेष धन्यवाद।

अव्यवहारिक प्रकार - निरर्थक और निर्दयी

दलदल सॉर्ट (BogoSort)

Bozo जोकर सॉर्ट (BozoSort)

क्रमपरिवर्तन क्रमबद्ध (PermSort)

सिली सॉर्ट (स्टॉग सॉर्ट)

छँटाई बाबुशकिना (बाबुश्किन सॉर्ट)

More articles: