स्ट्रिंग्स के लिए इस तरह की बिटवाइज़ एमएसडी छँटाई "तेज" है। हालाँकि, एल्गोरिथ्म को शाब्दिक विशेषज्ञता के लिए नामित नहीं किया गया है। लेखक एलन बीचिक ने खुद के बाद नाम चुना, एबीसीन का मतलब एलन बीकिक कैरेक्टर सॉर्ट है ।

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

एल्गोरिथ्म के लिए, यह एकमात्र ऐसा प्रकार है जिसके बारे में मुझे पता है, जिसके उपयोग के लिए इसके आविष्कारक को धन की आवश्यकता होती है।

Bichik

रूढ़िवादी बैपटिस्ट, कट्टरता के कट्टर विरोधी। विरोध करने वाले विधर्मियों को एलन द्वारा 30 साल पहले अपनी सबसे अधिक बिकने वाली पुस्तक, एस्केंशन अहेड ऑफ ग्रेट ट्राइब्यूलेशन (1980 में प्री-क्लेश रिपीट्योर, 1999 में पुनर्मुद्रित) द्वारा कुचल दिया गया था। हमारे नायक के कई वर्षों के धार्मिक शोध का नतीजा यह है कि " द सोल्यूशन ऑफ़ द एसेन्शन - द पज़लिंग द पज़ल टू द पज़ल " (" The Rapture Solution, पॉटिंग द पज़ल एक साथ ") पुस्तक है।

लाभ

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

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

सामान्य तौर पर, उपरोक्त सभी सत्य है। सच है, तुलना, आदान-प्रदान और सहायक तत्वों के बजाय, कोई भी सरल कह सकता है - यह वितरण द्वारा छंटनी है। खैर, "स्मृति की अर्थव्यवस्था" के बारे में भी बहस की जा सकती है (लेकिन बाद में और अधिक)।

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

एल्गोरिथ्म

छंटनी के लिए दो सहायक सरणियों की आवश्यकता होती है।

हम उनमें से एक को एक शब्द ट्रैकर (WT - शब्द ट्रैकर) कहेंगे, इसकी मदद से हम ऐसे शब्दों को समूहित करेंगे जिनके i- वें श्रेणी में समान अक्षर हैं। पाए गए पहले ऐसे शब्द के लिए, मान 0 सूची में दर्ज किया गया है। i- th श्रेणी में समान अक्षर के साथ पाए गए प्रत्येक बाद के शब्द के लिए, उसी विशेषता के अनुरूप पिछले शब्द का सूचकांक शब्द ट्रैकर में चिह्नित है।

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

एक अन्य सरणी वर्ण ट्रैकर (LT - लेटर ट्रैकर) है। यह सूची में बहुत पहले (या अंतिम) शब्द के सूचकांकों को चिह्नित करता है, जिसमें एक निश्चित चरित्र संबंधित श्रेणी में होता है। इस शब्द के आधार पर, शब्द ट्रैकर की मदद से, ith अंक में संबंधित पत्र के साथ अन्य सभी टोकन की श्रृंखला को बहाल किया जाता है।

अब तालिका सूची से अंतिम शब्दों के सूचकांकों को दिखाती है जो एक अक्षर या किसी अन्य से शुरू होते हैं।

दिए गए क्षण में, इन दो तालिकाओं का उपयोग करके, आप सभी शब्दों को बाहर निकाल सकते हैं, उदाहरण के लिए, "बी" अक्षर से शुरू होता है। ऐसा करने के लिए, सेल मान LT [1, b] = 9 लें - यह "b" - बेकी से शुरू होने वाली सूची से अंतिम शब्द का सूचकांक है। इस शब्द का अब ट्रैकर शब्द में ट्रैक मान है: WT [9] = 8 । यह "बी" पर पिछले शब्द का सूचकांक है - बेलिंडा। मान 6 सेल WT [8] में संग्रहीत किया जाता है - बारबरा को इस सूचकांक के तहत पाया जाता है, जो बदले में बीट्रिक्स मैट्रिक्स को इंगित करता है: WT [6] = 3 । बीट्रिक्स के लिए ट्रैक मान शून्य है, अर्थात इसके सापेक्ष, सूची में बी के साथ शुरू होने वाले पिछले शब्द नहीं हैं।

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

C ++ डेमो कोड (लेखक - लिन डी। यारब्रॉन)

/* ** ABCsort  C **         **   (Allen Beechick)      , **  №5218700. **        . **    : **  .  (Lynn D. Yarbrough) **   (Palm Desert),  **====================================================================== */ #include <malloc.h> #include <stdio.h> #include <stdlib.h> long *RT; /*   */ long **LT; /*   */ void ABCsort (int keys) { /*     */ void process (int, int); long register i, j, recno; int register c; int nodup = noduplicates; long start, step, stop; /*      */ LT = lmatrix(1, keys, alphamin, alphamax); RT = lvector(1, N); /*   : */ for (j = alphamin; j <= alphamax; j++) { for (i = 1; i <= keys; i++) LT[i][j] = 0; } /*    */ if ((keys & 1) ^ nodup) { start = N; stop = 0; step = -1; } else { start = 1; stop = N + 1; step = 1; } /*  1 */ /*      */ for (recno = start; recno != stop; recno += step) { c = GetNextField(recno, 1); RT[recno] = LT[1][c]; LT[1][c] = recno; } /*       . */ process(1, keys); free_lmatrix(LT, 1, keys, alphamin, alphamax); free_lvector(RT, 1, N); } /* ======================================================== */ /*     1- : */ /*  ,       */ void process (int level, int keys) { long i, newlevel, nextrec, recno; int nodup = noduplicates; unsigned char c; /*    */ for (i = alphamin; i <= alphamax; i++) { /*   i-  */ recno = LT[level][i]; LT[level][i] = 0; /*      */ while (recno != 0) { /* i-    ,        */ if (RT[recno] == 0) { PutCurrRecord(recno); recno = 0; continue; } else { /*     i- : */ if (level == keys) { /*      : */ while (recno != 0) { /*       */ PutCurrRecord(recno); recno = RT[recno]; if (nodup) recno = 0; } } else { /*    :*/ /*     */ newlevel = level + 1; while (recno != 0) { nextrec = RT[recno]; c = GetNextField(recno, newlevel); RT[recno] = LT[newlevel][c]; LT[newlevel][c] = recno; recno = nextrec; } /*    */ process(newlevel, keys); } } } } }

एनीमेशन का Youtube संस्करण

समय की जटिलता

सामान्य तौर पर, हम आत्मविश्वास से औसत समय जटिलता ओ (k * n) के बारे में बात कर सकते हैं, जहां k संसाधित बिट्स की संख्या है।

एकीकृत सर्किट के विकास में लगी कंपनी " ASIC DESIGN & MARKETING " ने PPVM ( यूजर-प्रोग्रामेबल गेट एरे ) बनाते समय एल्गोरिथम को लागू किया। कंपनी के इंजीनियरों के अनुसार, एबीसीसॉर्ट क्विकॉर्ट की तुलना में 2.5 से 10 गुना तेज है। यह इस पीडीएफ रिपोर्ट में पाया जा सकता है।

स्मृति कठिनाई

छंटाई के लिए दो सहायक सरणियों की आवश्यकता होती है: चरित्र ट्रैकर के लिए दो-आयामी, जिसे जटिलता का आकलन करते समय उपेक्षित किया जा सकता है। और शब्द ट्रैकर के लिए n तत्वों की एक सरणी भी। अर्थात्, अतिरिक्त मेमोरी के लिए समग्र रेटिंग O (n) है ।

कीमत

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

छंटाई की कीमत काफी दिव्य है, 49 डॉलर है। इस राशि के लिए, एक संतुष्ट ग्राहक प्राप्त करता है:

BeechickSort.dll । इसमें एक सॉर्टिंग फ़ंक्शन होता है जिसे किसी भी प्रोग्राम से कॉल किया जा सकता है।
BeechickSortDemo.exe , और साथ ही इसके प्रकार - BeechickSortDemo.cpp ।
सॉर्टिंग के लिए इनपुट डेटा के उदाहरण: SchoolAddresses.txt (कई क्षेत्रों के साथ रिकॉर्ड, आप उन्हें अलग-अलग तरीकों से सॉर्ट कर सकते हैं) और ShuffledText.txt (एक शब्दकोश से यादृच्छिक शब्दों का एक सेट)।
SortDemo.htm - छँटाई विकल्पों की स्थापना के लिए एक वेब इंटरफ़ेस।

यदि आप शीर्ष पर 39 सशर्त इकाइयाँ फेंकते हैं, तो DLL C ++ में टिप्पणी किए गए स्रोतों के साथ वापस आ जाएगा।

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

जिन लोगों के पेटेंट के बारे में सवाल हैं, उनके लिए एलन बीकिक व्यापक जवाब देते हैं:

शायद आपको Microsoft को एल्गोरिथम बेचना चाहिए?

मैंने कोशिश की। इससे पहले कि मुझे पेटेंट मिलता। Microsoft के लोगों ने कहा कि वे पेटेंट नहीं कर पाएंगे, क्योंकि यह दूसरी तरह की बिटवाइज़ छँटाई है; इसके अलावा, उसने उन्हें प्रभावित नहीं किया। लेकिन पेटेंट कार्यालय ने एल्गोरिथ्म की विशिष्टता को समझा।

आप एल्गोरिथ्म को सार्वजनिक डोमेन में क्यों नहीं रखते हैं?

एक पेटेंट वकील बिना किसी कारण के काम नहीं करता है। सरकारी सेवा मुफ्त में पेटेंट नहीं देती है। इसलिए, अपनी जेब से खर्च किए गए धन का कम से कम हिस्सा लौटाएं।

एल्गोरिदम के लक्षण

समय की जटिलता	सबसे खराब	मध्यम	सबसे अच्छा
नाम	एबीसी सॉर्टिंग (एबीसीसॉर्ट, एलन बिछिक कैरेक्टर सॉर्ट); बीचक तरहक
लेखक	एलेन बीचिक
प्रकाशन का वर्ष	1993
वर्ग	वितरण क्रमबद्ध करें
उपवर्ग	बिट सॉर्ट
स्थिरता	नियमित
तुलना	कोई तुलना नहीं
समय की जटिलता	*ओ (के एन)**	*ओ (के एन)**	ओ (एन)
स्मृति कठिनाई	ओ (एन)

संदर्भ

साइट सॉर्ट करें (वेब संग्रह)
लिन डी। यारब्रोब का C ++ में कार्यान्वयन (वेब-आर्काइव)
एल्गोरिथम पेटेंट (पीडीएफ)
एकीकृत परिपथों में हार्डवेयर कार्यान्वयन (पीडीएफ)

एलन बीचिक

फेसबुक पर
लिंक्डइन पर
पुस्तक की साइट "The Key to Ascension - पहेली को एक साथ रखना"

एबीसी प्रकार