ओ (एन) जटिलता के साथ बिटसॉर्टरिंग एल्गोरिथम

प्रागितिहास

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

कल्पना कीजिए कि हमारे पास निम्नलिखित संख्याएँ हैं:

• 123
• 12345
• 22,345
• 12345678
• 1

हम, मानव के रूप में इस डेटा ऐरे को कैसे क्रमबद्ध करेंगे? यह सही है, हम सबसे अधिक नेत्रहीन लंबी संख्या का चयन करेंगे।
और अगर लंबाई समान है, तो हम एक श्रेणी में संख्याओं की तुलना करेंगे। मुझे लगा कि आप बस कंप्यूटर का काम कर सकते हैं।

एल्गोरिथ्म

इसलिए, हमारे पास इनपुट संख्या N के आकार की एक सरणी है:

int[] array = new int[n] 

अगला, हम सरणी के प्रत्येक तत्व को बाइनरी फॉर्म में दर्शाते हैं और इसे एक नई सूची में सहेजते हैं:

 bool[][] bitMatrix = new bool[n][]; //    for (int i = 0; i < array.Length; i++) { BitArray bitArray = new BitArray (new int[1]{ array [i] }); bool[] bits = new bool[bitArray.Length]; bitArray.CopyTo (bits, 0); Array.Reverse (bits); bitMatrix [i] = bits; } 

हमें निम्नलिखित मैट्रिक्स मिली:


फिर सबसे दिलचस्प हिस्सा आता है: पुनरावर्ती छंटाई।
आरंभ करने के लिए, आइए देखें कि हम इस बिट मैट्रिक्स को कैसे सॉर्ट करेंगे:

1. हम पहले कॉलम को देखते हैं
2. हम उन सभी तत्वों का चयन करते हैं जहां पहली बिट एक सूची में 1 है
3. हम उन सभी तत्वों का चयन करते हैं जहां दूसरी सूची में पहला बिट 0 है
4. पहली और दूसरी सूची के लिए चरण 2 और 3 को दोहराएं, लेकिन पहले से ही कॉलम नंबर दो के लिए

कोड इस तरह दिखेगा:

 private void SortAlgorithm(bool[][] bitMatrix, int columnNumber) { List<bool[]> ones = new List<bool[]> (); List<bool[]> zeros = new List<bool[]> (); for (int i = 0; i < bitMatrix.Length; i++) { if (bitMatrix[i][columnNumber]) ones.Add(bitMatrix[i]); else zeros.Add(bitMatrix[i]); } columnNumber++; if (columnNumber == MAX_COLUMN_COUNT)//MAX_COLUMN_COUNT = sizeof(int)*8 { sortedBitMatrix.AddRange(ones); sortedBitMatrix.AddRange(zeros); return; } if (ones.Count != 0) SortAlgorithm (ones.ToArray(), columnNumber); if (zeros.Count != 0) SortAlgorithm (zeros.ToArray(), columnNumber); } 

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

 private int[] ConvertBitMatrixToArray(List<bool[]> bitMatrix) { int[] resultArray = new int[bitMatrix.Count]; int count = 0; for (int i = 0; i < bitMatrix.Count; i++) { bool[] bits = bitMatrix [i]; Array.Reverse(bits); BitArray bitArray = new BitArray(bits); int[] tmpArray = new int[1]; bitArray.CopyTo(tmpArray, 0); resultArray [count] = tmpArray [0]; count++; } return resultArray; } 

विधि का परिणाम एक क्रमबद्ध सरणी होगा।

लेकिन समानांतरकरण का क्या?

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

जटिलता

दिए गए सरणी को क्रमबद्ध करने के लिए, हमें निम्नलिखित पुनरावृत्तियों की आवश्यकता है:

1. एक बिट मैट्रिक्स बनाना: एन
2. शून्य और लोगों के लिए खोजें: 32n
3. परिवर्तित क्रमबद्ध बिट मैट्रिक्स: एन

कुल: 34 एन, जो हे (एन) है

आपकी राय दिलचस्प है।
आपका ध्यान देने के लिए धन्यवाद।

PS github.com/koljaka/BitSorting