Google ड्राइव ( AlgoLab (Excel 2007-2013) .xlsm और AlgoLab (Excel 97-2003) .xls फ़ाइलों से AlgoLab डाउनलोड करें।

बोल्शेविकों के बारे में इतने लंबे समय से क्या बात हो रही है और जो मैं कई वर्षों से एक अलग गति से कर रहा हूं वह आखिरकार हुआ है। कुछ साल पहले, उन्होंने habrastaty के लिए एल्गोरिदम जीआईएफ-एनीमेशन बनाने के लिए एक छोटा मैक्रो लिखा था। समय के साथ, मेरा विनम्र उपकरण एक प्रभावशाली आकार में विकसित हो गया है, जो दुनिया को प्रकट करने के लिए अब शर्म की बात नहीं है।

इसलिए मिलते हैं।

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

उत्पन्न एनीमेशन के उदाहरण

बाइनरी ट्री छँटाई

स्पेगेटी छँटाई

नींद की तरह

केवल 4 शीट - 2 मुख्य और 2 इसलिए, सूचनात्मक। यहाँ वे हैं:

चादर को क्रमबद्ध करें		प्रोसेस शीट



शीट को क्रमबद्ध करें		शीट ग्राफ

_{एक तस्वीर पर क्लिक करने से एक पूर्ण आकार की छवि खुल जाएगी}

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

आइए इन चादरों से और अधिक विस्तार से परिचित हों।

चादर को क्रमबद्ध करें

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

पहली पंक्ति में ही सरणी है। यदि आवश्यक हो, तो आप इसमें व्यक्तिगत तत्वों के मूल्यों को मैन्युअल रूप से बदल सकते हैं:

ऊपरी बाईं ओर, आपको उत्पन्न सरणी के लिए मुख्य विशेषताओं को निर्दिष्ट करने की आवश्यकता है:

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

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

थोड़ी सी दाईं ओर वह क्षेत्र है जिसमें आप यह निर्दिष्ट कर सकते हैं कि जनरेट किए गए अनसोल्ड सरणी में तत्वों को कैसे ठीक किया जाए।

अनियमित मिश्रित सरणी उत्पन्न करें? या शायद तत्वों को अवरोही क्रम में व्यवस्थित करें? या सरणी को लगभग क्रमबद्ध करें (और लगभग छँटाई के गुणांक को भी निर्दिष्ट करें)?

इनमें से किसी भी विधि का चयन करने के लिए, आपको केवल आइटम के साथ सेल पर क्लिक करना होगा। परिणामस्वरूप, सरणी को पहली पंक्ति में पुनर्जीवित किया जाता है। चयनित सेल नीला हो जाएगा।

बाईं ओर वह क्षेत्र है जिसकी आवश्यकता तब होगी जब आपको न केवल विज़ुअलाइज़ेशन की प्रशंसा करने की आवश्यकता होगी, बल्कि संपूर्ण प्रक्रिया फ़्रेम-बाय-फ़्रेम को छवियों के रूप में सहेजने के लिए भी।

सबसे पहले, आपको यह निर्दिष्ट करने की आवश्यकता है कि छवियों के लिए सामान्य रूप से सॉर्टिंग चरणों को निर्यात करना है (= 0, यदि नहीं, तो = 1 यदि हां, और यह विकल्प "एक बार" है, अर्थात, यह सॉर्टिंग पूरा होने के बाद शून्य पर रीसेट हो जाता है)। दूसरे, आपको छवि प्रारूप निर्दिष्ट करने की आवश्यकता है (केवल 4 विकल्प संभव हैं: जीआईएफ, जेपीजी, पीएनजी और बीएमपी। अंतिम विकल्प उच्चतम गुणवत्ता परिणाम देता है, इसलिए मैं इसकी सलाह देता हूं)। तीसरा, आपको उस फ़ोल्डर को पथ निर्दिष्ट करना होगा जहां छवियों को बचाने के लिए (इस सेल पर क्लिक करें और एक निर्देशिका चुनने के लिए एक डायलॉग बॉक्स खुलेगा)। इसके बाद सेल आता है कि मैक्रो अपने आप में भर जाता है - सत्र पहचानकर्ता (इस विशेष सॉर्टिंग एप्लिकेशन के फ्रेम को बचाने के लिए सबफ़ोल्डर के अनूठे नाम के लिए आवश्यक)। और कब्जा क्षेत्र को सही ढंग से निर्दिष्ट करने के लिए भी आवश्यक है (ऊपरी बाएं और निचले दाएं कोशिकाओं के निर्देशांक, यह उन फ्रेम होंगे जो उनके लिए सीमित होंगे - पूरी शीट की प्रतिलिपि नहीं बनाते हैं?)

ठीक है, बहुत दाहिने हिस्से में आपको "सॉर्ट" सेल मिलेगा (जो प्रक्रिया शुरू करने के लिए एक बटन के रूप में कार्य करता है, जब एक सरणी को चुनना और बनाना होता है, तो बस उस पर क्लिक करें)।

यहां तक कि इस बटन के बगल में विभिन्न विशेष वर्ण रहते हैं जिनका उपयोग विज़ुअलाइज़ेशन में किया जा सकता है। इन कोशिकाओं को छूने की जरूरत नहीं है।

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

80 से अधिक एल्गोरिदम में से, लगभग आधे आज उपलब्ध हैं। अब तक, पहले से ही लागू लोगों की तुलना में अवास्तविक लोगों की एक पीला उपस्थिति है। मैं अभी भी कुछ करने में कामयाब नहीं हुआ (और कार्यान्वयन शुरू भी नहीं किया है)। कुछ का विकास चल रहा है। उनमें से कुछ लिखित और परीक्षण किए गए हैं और बहुत जल्द ही उपलब्ध होंगे (विशेष रूप से, आवेषण द्वारा लगभग सभी छंटनी मेरे लिए तैयार हैं, हालांकि, मैं उन्हें आवेदन में जोड़ दूंगा क्योंकि आने वाले हफ्तों में इन छंटनी के लिए habrastats जारी किए जाते हैं और अद्यतन AlgoLab.xlsm साझा करें - और क्या करना है, मैं अपनी श्रृंखला के नए एपिसोड को खराब नहीं करना चाहता)।

मैं पहले से लागू छंटनी में से कुछ को संशोधित करने की योजना बना रहा हूं। विज़ुअलाइज़ेशन मुझे हर जगह संतुष्ट नहीं करता है।

लेकिन इस क्षेत्र में, एक एल्गोरिथ्म चुनते समय, इसके बारे में सारांश जानकारी लोड की जाती है। जानकारी "सॉर्ट" शीट से ली गई है, यह स्वचालित रूप से एक मैक्रो के साथ वापस ले लिया गया है। वैसे, यदि आप इस क्षेत्र में पाठ बदलते हैं, तो मूल शीट पर यह भी बदल जाएगा।

सॉर्ट करें, जैसा कि आप बहुत कुछ देख सकते हैं। इस सभी वैभव में भ्रमित न होने के लिए, उन्हें कक्षाओं में विभाजित किया जाता है, जिसके आधार पर डेटा को व्यवस्थित करने की मौलिक पद्धति का उपयोग किया जाता है। ये वर्ग क्या हैं?

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

आगामी हेरास्टिंग में, प्रत्येक वर्ग के लिए विस्तृत बारीकियों पर प्रकाश डाला जाएगा। खैर, हम अगली शीट पर जाते हैं।

प्रोसेस शीट

दरअसल, ऐरे को जेनरेट करते समय, अल्गोरिथम को चुनने और "सॉर्ट" बटन पर क्लिक करने पर, मैक्रो इस शीट पर फेंकता है। यह यहां है कि डेटा को व्यवस्थित करने का रहस्य क्या है।

ऊपर पूरी प्रक्रिया के दौरान आप इस अद्भुत खिड़की के साथ होंगे:

चूंकि देखने का चरण चरण-दर-चरण है, इसलिए अगले चरण पर आगे बढ़ने के लिए, "नया चरण" बटन पर क्लिक करना आवश्यक है। माउस के साथ ऐसा करना बहुत सुविधाजनक नहीं है, इसलिए विंडो इनपुट का ध्यान हमेशा इस बटन पर होता है। यही है, अगले चरणों पर जाने के लिए, आपको बस Enter कीबोर्ड दबाने के लिए आलसी होने की आवश्यकता नहीं है (कोई अन्य इशारों की आवश्यकता नहीं होगी)।

"समाप्त" बटन चरण-दर-चरण दृश्य से प्रक्रिया को प्रदर्शित करता है। एल्गोरिथ्म चुपचाप अपना काम पूरा करेगा और केवल अंतिम परिणाम दिखाएगा। आप सॉर्टिंग ऑपरेशन के अंतिम चरण को नहीं देखेंगे।

"एबॉर्ट" बटन इस कदम पर मैक्रोज़ के काम को पूरी तरह से रोक देता है।

"स्नैपशॉट" बटन आपको इस विशेष चरण के स्क्रीनशॉट को सहेजने की अनुमति देता है। फिर आपको उस फ़ोल्डर में चित्र मिलेगा जो सॉर्ट शीट पर सेटिंग्स में निर्दिष्ट है।

शीट को क्रमबद्ध करें

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

शीट ग्राफ

इस शीट पर आप मेरी कल्पनाओं से परिचित हो सकते हैं कि किस प्रकार के बारे में सबसे नज़दीकी हैबस्ट्रेटिक रिलीज़ की तारीखों के बारे में।

मैं इस क्रम में एल्गोरिदम के बारे में बात करूंगा।

आदान-प्रदान → सम्मिलन → चयन → विलय → वितरण →
→ हाइब्रिड्स → समानांतर → नेटवर्क → रैंडम

सामान्य वर्गों को सूचीबद्ध किया गया है, लेकिन सामान्य तौर पर, कई सामान्य लोग इस तरह की सामान्य योजना का पालन करने से मना कर देते हैं।

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

व्यावहारिक क्रमबद्ध तुलना

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

पायथन की चर की स्मृति तक पहुँचने की अपनी प्रणाली है (विशेषकर यदि ये चर एक दूसरे को सौंपे जाते हैं), यही वजह है कि अनुकूलित एल्गोरिदम धीमा चला सकते हैं।

बौना क्रमबद्ध	अनुकूलित बौना क्रमबद्ध

`def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data`	`def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data`
1000 तत्वों में से 10 सरणियाँ
कुल समय: 3.39134 सेकंड।	कुल समय: 5.6809 सेकंड।

शेकर / बबल के साथ एक समान स्थिति। अपेक्षाओं के विपरीत, बबल सॉर्टिंग शेकर सॉर्टिंग की तुलना में तेजी से काम करती है (हालांकि शेकर सॉर्ट एक बेहतर बुलबुला सॉर्ट है)।

नियंत्रण के लिए, मैंने PHP में भी छंटनी का परीक्षण किया (मैं मुख्य रूप से इस भाषा में काम करता हूं, इसलिए एक वैकल्पिक परीक्षण तेजी से और इस पर बनाना आसान था)। वहां स्थिति पहले से ही "सामान्य" है - सभी डेटा सेटों पर अनुकूलित "सूक्ति" स्पष्ट रूप से सामान्य से अधिक तेजी से काम करता है।

हालांकि, PHP में "अपूर्ण" और एक धीमा उपकरण होने की भी प्रतिष्ठा है, इसलिए मैंने फैसला किया कि यह वैश्विक निष्कर्ष के लिए भी उपयुक्त नहीं है। [वास्तविक गति का परीक्षण करने के लिए गलत भाषा को चुनने में] संभव रिप्रॉसेस को कम करने के लिए, मैंने मुख्य परीक्षणों को भी जावा में कम से कम करने का फैसला किया। हालाँकि, मैं इस भाषा के लिए अपने ज्ञान की कमी में भाग गया। काश, यह एक साथ नहीं बढ़ता।

इस प्रकार, परीक्षण तुरंत दो दो भाषाओं में होगा:

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

बेशक, सभी भाषाओं में सभी विकल्प साझा किए जाएंगे।

पूछे जाने वाले प्रश्न

मैं पहले से ही दर्शकों से कुछ सवाल पूछता हूं, मैं तुरंत जवाब दूंगा।

एक्सेल में एल्गोरिदम को विज़ुअलाइज़ करने का कार्यक्रम क्यों है?

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

ठीक है, चलो इन सभी प्रकारों पर एक नज़र डालें। आगे क्या है?

एल्गोलैब के आधार पर मैं पेड़ों, रेखांकन के लिए विज़ुअलाइज़ेशन करूंगा। उलम की मेज़पोश, लैंग्टन की चींटी, बस इतना ही। 2048 के लिए अभी भी रिक्त हैं (एआई मिनिमैक्स और मोंटे कार्लो विधि का उपयोग करके खेलता है - आपको इसे समाप्त करने की आवश्यकता है)। वर्क्स बहुत भूमि है।

संदर्भ

Google ड्राइव ( AlgoLab (Excel 2007-2013) .xlsm और AlgoLab (Excel 97-2003) .xls फ़ाइलों से AlgoLab डाउनलोड करें।

हर समय के सॉर्ट