ब्लॉक सॉर्ट

ब्लॉक सॉर्ट
	ब्लॉक सॉर्ट स्थिर रूप से संख्याओं 1 से 16 तक सॉर्ट करें।; 16 के समूहों को सम्मिलित करें, दो आंतरिक बफ़र्स निकालें, A ब्लॉक को टैग करें (आकार का √16 = 4 प्रत्येक), A ब्लॉक को B के माध्यम से रोल करें, उन्हें स्थानीय रूप से मर्ज करें, दूसरे बफ़र को सॉर्ट करें, और बफ़र्स को फिर से वितरित करें।
Class	सोर्टिंग एल्गोरिदम
Data structure	सरणी
Worst-case performance	O(n log n)
Best-case performance	O(n)
Average performance	O(n log n)
Worst-case space complexity	O(1)

ब्लॉक सॉर्ट, या ब्लॉक मर्ज सॉर्ट, सोर्टिंग एल्गोरिदम है जो $O (n log n)$ इन-प्लेस स्थिर सॉर्टिंग पर पहुंचने के लिए एक निवेशन सॉर्ट के साथ कम से कम मर्ज एल्गोरिदम संचालन को साथ जोड़ता है। अतः इसका नाम इस अवलोकन से मिलता है कि दो क्रमबद्ध सूचियों, A और B को मर्ज करना, A को समान आकार के ब्लॉक में तोड़ने, विशेष नियमों के अंतर्गत प्रत्येक A ब्लॉक को B में डालने और AB युग्म को मर्ज करने के बराबर है।

इस प्रकार से 2008 में पोक-सोन किम और अर्ने कुट्ज़नर द्वारा स्थान मर्ज में O(log n) के लिए व्यावहारिक एल्गोरिदम प्रस्तावित किया गया था।^[1]

अवलोकन

ब्लॉक सॉर्ट का बाह्य पाश समानयन मर्ज सॉर्ट के समान है, जहां सॉर्ट का प्रत्येक स्तर 1, फिर 2, फिर 4, 8, 16 और इसी प्रकार के आकार में उपसरणी, A और B के युग्म को मर्ज करता है। जब तक दोनों उपसरणी संयुक्त न हो जाएं तब तक वह सारणी ही नहीं होती।

इस प्रकार से पारंपरिक विधियों के जैसे A और B को सीधे मर्ज करने के अतिरिक्त, एक ब्लॉक-आधारित मर्ज एल्गोरिदम A को आकार √Aके अलग-अलग ब्लॉकों में विभाजित करता है (परिणामस्वरूप √Aब्लॉक की संख्या भी), प्रत्येक A ब्लॉक को B में इस प्रकार सम्मिलित करता है कि प्रथम मान प्रत्येक A ब्लॉक का मान इसके तुरंत बाद B मान से कम या बराबर (≤) है, फिर स्थानीय रूप से प्रत्येक A ब्लॉक को इसके और अगले A ब्लॉक के बीच किसी भी B मान के साथ मर्ज कर देता है।^[2]

चूंकि मर्ज के लिए अभी भी A ब्लॉक को मर्ज करने के लिए एक अलग बफर की आवश्यकता होती है, इसलिए सरणी के भीतर दो क्षेत्र इस उद्देश्य के लिए आरक्षित होते हैं (आंतरिक बफर के रूप में जाना जाता है)।^[3] इस प्रकार पहले दो A ब्लॉकों को A के भीतर प्रत्येक मान के पहले उदाहरण को सम्मिलित करने के लिए संशोधित किया गया है, यदि आवश्यक हो तो उन ब्लॉकों की मूल विवरण को स्थानांतरित कर दिया गया है। अतः शेष A ब्लॉक को फिर B में डाला जाता है और दो बफ़र में से एक को स्वैप स्थान के रूप में उपयोग करके मर्ज कर दिया जाता है। यह प्रक्रिया उस बफ़र में मानों को पुनर्व्यवस्थित करने का कारण बनती है।

इस प्रकार से एक बार जब प्रत्येक A और B उपसरणी के प्रत्येक A और B ब्लॉक को मर्ज सॉर्ट के उस स्तर के लिए मर्ज कर दिया जाता है, तो उस बफ़र में मानों को उनके मूल क्रम को पुनर्स्थापित करने के लिए सॉर्ट किया जाना चाहिए, इसलिए एक निवेशन सॉर्ट लागू किया जाना चाहिए। फिर बफ़र में मानों को सरणी के भीतर उनकी प्रथम क्रमबद्ध स्थिति में पुनः वितरित किया जाता है। यह प्रक्रिया बाह्य समानयन मर्ज सॉर्ट के प्रत्येक स्तर के लिए दोहराई जाती है, जिस बिंदु पर सरणी को स्थिर रूप से सॉर्ट किया गया होगा।

एल्गोरिथम

इस प्रकार से कोड उदाहरणों में निम्नलिखित संक्रियकों का उपयोग किया जाता है:

\|	bitwise OR
>>	shift right
%	modulo
++ and +=	increment
[x, y)	range से ≥ x और < y
\|range\|	range.end – range.start
array[i]	i-सरणी की वस्तु

अतः इसके अतिरिक्त, ब्लॉक सॉर्ट अपने समग्र एल्गोरिदम के भाग के रूप में निम्नलिखित संक्रियकों पर निर्भर करता है:

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

 Rotate(array, amount, range)

    Reverse(array, range)
    Reverse(array, [range.start, range.start + amount))
    Reverse(array, [range.start + amount, range.end))

दो की फलक घात: दो की अगली घात के लिए एक मान फलक करें। इस प्रकार 63 32 हो जाता है, 64 64 ही रहता है, इत्यादि।^[5]

FloorPowerOfTwo(x)
    x = x | (x >> 1)

    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)

    if (this isa  64-bit system)

        x = x | (x >> 32)
    return x - (x >> 1)

बाह्य पाश

इस प्रकार से जैसा कि पहले बताया गया है, ब्लॉक सॉर्ट का बाह्य पाश समानयन मर्ज सॉर्ट के समान है। यद्यपि, यह उस प्रकार से लाभान्वित होता है जो प्रत्येक को सुनिश्चित करता है, A और B उपसरणी वस्तु के भीतर समान आकार की होती है:

   BlockSort(array)

       power_of_two = FloorPowerOfTwo(array.size)

       scale = array.size/power_of_two // 1.0 ≤ scale <2.0
      
       // insertion sort 16–31 items at a time

       for (merge = 0; merge < power_of_two; merge += 16)
           start = merge * scale
           end = start + 16 * scale
           InsertionSort(array, [start, end))
      
       for (length = 16; length < power_of_two; length += length)
           for (merge = 0; merge < power_of_two; merge += length * 2)
               start = merge * scale
               mid = (merge + length) * scale
               end = (merge + length * 2) * scale
              
               if (array[end − 1] < array[start])
                   // the two ranges are in reverse order, so a rotation is enough to merge them
                   Rotate(array, mid − start, [start, end))
               else if (array[mid − 1] > array[mid])
                   Merge(array, A = [start, mid), B = [mid, end))
               // else the ranges are already correctly ordered

इस प्रकार से पैमाने के कारक को खंड integer_part + numerator/denominator के रूप में प्रस्तुत करके निश्चित-बिंदु अंकगणित का भी उपयोग किया जा सकता है:

   power_of_two = FloorPowerOfTwo(array.size)

   denominator = power_of_two/16
   numerator_step = array.size % denominator
   integer_step = floor(array.size/denominator)
  
   // insertion sort 16–31 items at a time
  
   while (integer_step < array.size)
       integer_part = numerator = 0
       while (integer_part < array.size)
           // get the ranges for A and B
           start = integer_part
          
           integer_part += integer_step
           numerator += numerator_step
           if (numerator ≥ denominator)
               numerator −= denominator
               integer_part++
          
           mid = integer_part
          
           integer_part += integer_step
           numerator += numerator_step
           if (numerator ≥ denominator)
               numerator −= denominator
               integer_part++
          
           end = integer_part
          
           if (array[end − 1] < array[start])
               Rotate(array, mid − start, [start, end))
           else if (array[mid − 1] > array[mid])
               Merge(array, A = [start, mid), B = [mid, end))
      
       integer_step += integer_step
       numerator_step += numerator_step
       if (numerator_step ≥ denominator)
           numerator_step −= denominator
           integer_step++

बफ़र निष्कर्ष

ब्लॉक सॉर्ट के लिए बफ़र निष्कर्षण प्रक्रिया।

इस प्रकार से मर्ज चरण के प्रत्येक स्तर के लिए आवश्यक दो आंतरिक बफ़र को A उपसरणी के भीतर उनके मानों के पहले 2√Aपहले उदाहरणों को A के प्रारंभ में ले जाकर बनाया जाता है। अतः सबसे पहले यह A में अवयवों पर पुनरावृत्त होता है और अद्वितीय मानों की गणना करता है इसकी आवश्यकता है, फिर यह उन अद्वितीय मानों को प्रारंभ में ले जाने के लिए सरणी घुमाव लागू करता है।^[6] इस प्रकार से यदि A में दो बफ़र (प्रत्येक √A आकार के) को भरने के लिए पर्याप्त अद्वितीय मान नहीं हैं, तो B का भी उपयोग किया जा सकता है। इस स्थिति में यह प्रत्येक मान के अंतिम उदाहरण को B के अंत तक ले जाता है, B के उस भाग को मर्ज के समय सम्मिलित नहीं किया जाता है।

while (integer_step < array.size)
    block_size = √integer_step

    buffer_size = integer_step/block_size + 1
    [extract two buffers of size 'buffer_size' each]

इस प्रकार से यदि B में पर्याप्त अद्वितीय मान नहीं हैं, तो यह सबसे बड़ी संख्या में अद्वितीय मान निकाल सकता है, फिर A और B ब्लॉक के आकार को समायोजित करता है ताकि परिणामी A ब्लॉक की संख्या कम या उसके बराबर हो। बफ़र के लिए अद्वितीय वस्तु निकाले गए। अतः इस स्थिति में मात्र एक बफ़र का उपयोग किया जाएगा - दूसरा बफ़र स्थित नहीं होगा।

buffer_size = [number of unique values found]

block_size = integer_step/buffer_size + 1
  
integer_part = numerator = 0

while (integer_part < array.size)
    [get the ranges for A and B]
    [adjust A and B to not include the ranges used by the buffers]

टैग A ब्लॉक

पहले आंतरिक बफ़र से मानों का उपयोग करके A ब्लॉक को टैग करना। ध्यान दें कि पहला A ब्लॉक और अंतिम B ब्लॉक असमान आकार के हैं।

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

// blockA is the range of the remaining A blocks,
// and firstA is the unevenly sized first A block
blockA = [A.start, A.end)

firstA = [A.start, A.start + |blockA| % block_size)
  
// swap the second value of each A block with the value in buffer1

for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size)
    Swap(array[buffer1.start + index], array[indexA])

    index++
  
lastA = firstA

blockB = [B.start, B.start + minimum(block_size, |B|))
blockA.start += |firstA|

रोल और ड्राप

दो A ब्लॉक B ब्लॉक से होकर गुजर रहे हैं। बार जब प्रथम A ब्लॉक पश्च छूट जाता है, तो असमान आकार का A ब्लॉक स्थानीय रूप से उसके बाद आने वाले B मानों के साथ मर्ज हो जाता है।

इस प्रकार से इस विधि से A ब्लॉक को परिभाषित करने और टैग करने के बाद, A ब्लॉक को अगले B ब्लॉक के साथ पहले समान आकार के A ब्लॉक को स्वैप करके B ब्लॉक के माध्यम से रोल किया जाता है। अतः यह प्रक्रिया तब तक दोहराई जाती है जब तक कि सबसे छोटे टैग मान वाले A ब्लॉक का प्रथम मान B ब्लॉक के अंतिम मान से कम या उसके बराबर न हो जाए जिसे अभी A ब्लॉक के साथ स्वैप किया गया था।

इस प्रकार से उस समय, न्यूनतम A ब्लॉक (सबसे छोटे टैग मान वाला A ब्लॉक) को रोलिंग A ब्लॉक के प्रारंभ में परिवर्तित कर दिया जाता है और टैग किए गए मान को पहले बफर से उसके मूल मान के साथ पुनः स्थापित किया जाता है। इसे ब्लॉक को पश्च छोड़ने के रूप में जाना जाता है, क्योंकि इसे अब शेष A ब्लॉक के साथ रोल नहीं किया जाएगा। अतः उस A ब्लॉक को पूर्व B ब्लॉक में डाला जाता है, पूर्व सूचकांक को खोजने के लिए बी पर बाइनरी सर्च का उपयोग करके और फिर उस सूचकांक के मान से कम या उसके बराबर है, और फिर उस सूचकांक पर A को B में घुमाकर।

   minA = blockA.start

   indexA = 0
  
   while (true)

       // if there's a previous B block and the first value of the minimum A block is ≤
       // the last value of the previous B block, then drop that minimum A block behind.
       // or if there are no B blocks left then keep dropping the remaining A blocks.
       if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0)
           // figure out where to split the previous B block, and rotate it at the split
           B_split = BinaryFirst(array, array[minA], lastB)

           B_remaining = lastB.end - B_split
          
           // swap the minimum A block to the beginning of the rolling A blocks

           BlockSwap(array, blockA.start, minA, block_size)
          
           // restore the second value for the A block

           Swap(array[blockA.start + 1], array[buffer1.start + indexA])
           indexA++
          
           // rotate the A block into the previous B block
           Rotate(array, blockA.start - B_split, [B_split, blockA.start + block_size))
          
           // locally merge the previous A block with the B values that follow it,
           // using the second internal buffer as swap space (if it exists)
           if (|buffer2| > 0)
               MergeInternal(array, lastA, [lastA.end, B_split), buffer2)
           else
               MergeInPlace(array, lastA, [lastA.end, B_split))
          
           // update the range for the remaining A blocks,
           // and the range remaining from the B block after it was split
           lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size)
           lastB = [lastA.end, lastA.end + B_remaining)
          
           // if there are no more A blocks remaining, this step is finished
           blockA.start = blockA.start + block_size
           if (|blockA| = 0)
               break
          
           minA = [new minimum A block] (see below)
       else if (|blockB| < block_size)
           // move the last B block, which is unevenly sized,
           // to before the remaining A blocks, by using a rotation
           Rotate(array, blockB.start - blockA.start, [blockA.start, blockB.end))
          
           lastB = [blockA.start, blockA.start + |blockB|)
           blockA.start += |blockB|
           blockA.end += |blockB|
           minA += |blockB|
           blockB.end = blockB.start
       else
           // roll the leftmost A block to the end by swapping it with the next B block
           BlockSwap(array, blockA.start, blockB.start, block_size)
           lastB = [blockA.start, blockA.start + block_size)
           if (minA = blockA.start)
               minA = blockA.end
          
           blockA.start += block_size
           blockA.end += block_size
           blockB.start += block_size
          
           // this is equivalent to minimum(blockB.end + block_size, B.end),
           // but that has the potential to overflow
           if (blockB.end > B.end - block_size)
               blockB.end = B.end
           else
               blockB.end += block_size
  
   // merge the last A block with the remaining B values
   if (|buffer2| > 0)
       MergeInternal(array, lastA, [lastA.end, B.end), buffer2)
   else
       MergeInPlace(array, lastA, [lastA.end, B.end))

इस प्रकार से एक अनुकूलन जिसे इस चरण के समय लागू किया जा सकता है वह है फ्लोटिंग-होल तकनीक।^[7] जब न्यूनतम A ब्लॉक को पश्च छोड़ दिया जाता है और उसे पूर्व B ब्लॉक में घुमाने की आवश्यकता होती है, जिसके बाद इसकी विवरण को स्थानीय मर्ज के लिए दूसरे आंतरिक बफर में परिवर्तित कर दिया जाता है, तो A ब्लॉक को पहले से ही बफर में स्वैप करना तीव्र होगा, और इस तथ्य का लाभ उठाने के लिए कि उस बफ़र की विवरण को कोई क्रम बनाए रखने की आवश्यकता नहीं है। इस प्रकार से इसलिए स्थिति सूचकांक पर दूसरे बफ़र (जो ब्लॉक स्वैप से पहले A ब्लॉक हुआ करता था) को पूर्व B ब्लॉक में घुमाने के अतिरिक्त, सूचकांक के बाद B ब्लॉक में मानों को मात्र बफ़र के अंतिम वस्तु के साथ ब्लॉक स्वैप किया जा सकता है।

अतः इस स्थिति में फ्लोटिंग होल सरणी के चारों ओर फ्लोटिंग दूसरे आंतरिक बफर की विवरण को संदर्भित करता है, और इस अर्थ में होल के रूप में कार्य करता है कि वस्तुओं को अपना क्रम बनाए रखने की आवश्यकता नहीं है।

स्थानीय मर्ज

इस प्रकार से एक बार जब A ब्लॉक को B ब्लॉक में घुमाया जाता है, तो पूर्व A ब्लॉक को उसके बाद आने वाले B मानों के साथ मर्ज कर दिया जाता है, दूसरे बफर को स्वैप स्थान के रूप में उपयोग किया जाता है। जब प्रथम A ब्लॉक पश्च गिराया जाता है तो इसका अर्थ प्रारंभ में असमान आकार का A ब्लॉक होता है, जब दूसरा A ब्लॉक उसके पश्च गिराया जाता है तो इसका अर्थ प्रथम A ब्लॉक होता है, इत्यादि।

MergeInternal(array, A, B, buffer)
    // block swap the values in A with those in 'buffer'
    BlockSwap(array, A.start, buffer.start, |A|)

    A_count = 0, B_count = 0, insert = 0
    while (A_count < |A| and B_count < |B|)
        if (array[buffer.start + A_count] ≤ array[B.start + B_count])
            Swap(array[A.start + insert], array[buffer.start + A_count])
            A_count++

        else
            Swap(array[A.start + insert], array[B.start + B_count])

            B_count++
        insert++

    // block swap the remaining part of the buffer with the remaining part of the array
    BlockSwap(array, buffer.start + A_count, A.start + insert, |A| - A_count)

इस प्रकार से यदि दूसरा बफ़र स्थित नहीं है, तो द्रढ़ता से इन-प्लेस मर्ज संचालन किया जाना चाहिए, जैसे कि ह्वांग और लिन एल्गोरिदम का घूर्णन-आधारित संस्करण,^[7]^[8] डुडज़िंस्की और डायडेक एल्गोरिदम,^[9] या बार-बार बाइनरी खोज और घूर्णन आदि।

MergeInPlace(array, A, B)
    while (|A| > 0 and |B| > 0)
        // find the first place in B where the first item in A needs to be inserted

        mid = BinaryFirst(array, array[A.start], B)

        // rotate A into place

        amount = mid - A.end
        Rotate(array, amount, [A.start, mid))

        // calculate the new A and B ranges
        B = [mid, B.end)
        A = [A.start + amount, mid)
        A.start = BinaryLast(array, array[A.start], A)

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

minA = blockA.start
for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size)

    if (array[findA + 1] < array[minA + 1])
        minA = findA

अतः ये शेष A ब्लॉक तब सरणी के माध्यम से घूमते रहते हैं और जहां वे हैं वहां गिराए और डाले जाते हैं। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि सभी A ब्लॉक हटाकर पूर्व B ब्लॉक में न घुमा दिए जाएं।

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

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

पुनर्वितरित

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

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

प्रकार

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

इस प्रकार से ब्लॉक सॉर्ट का संस्करण इसे प्रदान की गई अतिरिक्त मेमोरी की किसी भी मात्रा का उपयोग करने की अनुमति देता है, जब भी A इसमें फिट बैठता है तो A उपसरणी या A ब्लॉक को B के साथ मर्ज करने के लिए इस बाह्य बफर का उपयोग करता है। इस स्थिति में यह मर्ज सॉर्ट के समान होगा।

इस प्रकार से बफ़र आकार के लिए ठीक विकल्पों में सम्मिलित हैं:

आकार	टिप्पणियाँ
(count + 1)/2	एक पूर्ण-गति मर्ज सॉर्ट में परिवर्तित हो जाता है क्योंकि सभी A उपसरणी इसमें फिट होंगी
√(count + 1)/2 + 1	यह मर्ज के सबसे बड़े स्तर पर A ब्लॉक का आकार होगा, इसलिए ब्लॉक सॉर्ट किसी भी वस्तु के लिए आंतरिक या इन-प्लेस मर्ज का उपयोग करना छोड़ सकता है
512	मर्ज सॉर्ट के छोटे स्तरों पर कई मर्जों को संभालने के लिए एक निश्चित आकार का बफर पर्याप्त है
0	यदि प्रणाली कोई अतिरिक्त मेमोरी आवंटित नहीं कर सकता है, तो कोई भी मेमोरी ठीक रूप से कार्य नहीं करती है

इस प्रकार से आंतरिक बफ़र में से किसी की विवरण का उपयोग करके A ब्लॉक को टैग करने के अतिरिक्त, अप्रत्यक्ष गति-अनुकरण बफ़र का उपयोग किया जा सकता है।^[1]^[10] अतः यह आंतरिक बफर है जिसे s1 t s2 के रूप में परिभाषित किया गया है, जहां s1 और s2 प्रत्येक A और B ब्लॉक की संख्या के बराबर बड़े हैं, और t में s1 के तुरंत बाद कोई भी मान सम्मिलित है जो s1 के अंतिम मान के बराबर है (इस प्रकार यह सुनिश्चित होता है कि कोई नहीं) s2 में मान s1 में दिखाई देता है)। दूसरा आंतरिक बफ़र युक्त √A अद्वितीय मान अभी भी उपयोग किया जाता है। प्रथम √A फिर s1 और s2 के मानों को बफर में सूचना एन्कोड करने के लिए दूसरे के साथ स्वैप किया जाता है कि कौन से ब्लॉक A ब्लॉक हैं और कौन से B ब्लॉक हैं। जब इंडेक्स i पर A ब्लॉक को इंडेक्स j पर B ब्लॉक के साथ स्वैप किया जाता है, तो (जहां पहला समान आकार का A ब्लॉक प्रारंभ में सूचकांक 0 पर है), s1[i] और s1[j] को क्रमशः s2[i] और s2[j] के साथ स्वैप किया जाता है। इस प्रकार से यह B के माध्यम से A ब्लॉक की गतिविधियों का अनुकरण करता है। दूसरे बफर में अद्वितीय मानों का उपयोग A ब्लॉक के मूल क्रम को निर्धारित करने के लिए किया जाता है क्योंकि उन्हें B ब्लॉक के माध्यम से घुमाया जाता है। बार जब सभी A ब्लॉक हटा दिए जाते हैं, तो गति-अनुकरण बफर का उपयोग यह डिकोड करने के लिए किया जाता है कि सरणी में दिया गया ब्लॉक A ब्लॉक है या B ब्लॉक, प्रत्येक A ब्लॉक को B में घुमाया जाता है, और दूसरे आंतरिक बफर का उपयोग किया जाता है, जो स्थानीय मर्जों के लिए स्वैप स्थान के रूप में है।

इस प्रकार से प्रत्येक A ब्लॉक के दूसरे मान को टैग करने की आवश्यकता नहीं है - इसके अतिरिक्त पहले, अंतिम, या किसी अन्य अवयव का उपयोग किया जा सकता है। यद्यपि, यदि प्रथम मान टैग किया गया है, तो न्यूनतम A ब्लॉक को कहां छोड़ना है, यह निर्धारित करते समय मानों को पहले आंतरिक बफर (जहां उन्हें स्वैप किया गया था) से पढ़ने की आवश्यकता होगी।

अतः दूसरे आंतरिक बफ़र की विवरण को सॉर्ट करने के लिए कई सॉर्टिंग एल्गोरिदम का उपयोग किया जा सकता है, जिसमें शीघ्र से सुलझाएं जैसे अस्थिर सॉर्ट भी सम्मिलित हैं, क्योंकि बफ़र की विवरण अद्वितीय होने की गारंटी है। यद्यपि, स्थितिजन्य निष्पादन और पुनरावृत्ति की कमी के कारण निवेशन सॉर्ट की अभी भी अनुशंसा की जाती है।

विश्लेषण

इस प्रकार से ब्लॉक सॉर्ट एल्गोरिदम का ठीक रूप से परिभाषित और परीक्षण योग्य वर्ग है, जिसमें मर्ज और सॉर्ट के रूप में कार्यशील कार्यान्वयन उपलब्ध हैं।^[11]^[12]^[13] इससे इसकी विशेषताओं को मापने और विचार करने की अनुमति मिलती है।

जटिलता

अतः ब्लॉक सॉर्ट के प्रारंभ सरणी में 16-31 वस्तुओं के समूहों पर निवेशन सॉर्ट करने से होती है। निवेशन सॉर्ट $O(n^{2})$ संचालन है , इसलिए यह $O(16^{2}\times n/16)$ से $O(31^{2}\times n/31)$ तक कहीं भी ले जाता है, जो कि $O(n)$ है। इस प्रकार से मर्ज के प्रत्येक स्तर के पूर्ण होने के बाद इसे दूसरे आंतरिक बफ़र पर प्रविष्टि सॉर्ट भी लागू करना होगा। यद्यपि, चूँकि यह बफ़र आकार में ${\sqrt {A}}$ तक सीमित था, $O{\sqrt {n}}^{2}$ संचालन भी $O(n)$ में समाप्त होता है।

इसके बाद इसे मर्ज सॉर्ट के प्रत्येक स्तर के लिए दो आंतरिक बफ़र निकालने होंगे। यह A और B उपसरणी में वस्तुओं पर पुनरावृत्ति करके और जब भी मान परिवर्तित करता है तो गणना बढ़ाकर ऐसा करता है, और पर्याप्त मान मिलने पर यह उन्हें A के प्रारंभ या B के अंत में घुमाता है। इस प्रकार से सबसे निकृष्ट स्थिति में यह ${\sqrt {A}}$ गैर-सन्निहित अद्वितीय मान खोजने से पहले संपूर्ण सरणी की खोज करेगा, जिसके लिए ${\sqrt {A}}$ मानों के लिए $O(n)$ तुलना और ${\sqrt {A}}$ घूर्णन की आवश्यकता होती है। यह $O(n+{\sqrt {n}}\times {\sqrt {n}})$ , या $O(n)$ हल होता है।

अतः जब A या B उपसरणी में से से किसी में भी आंतरिक बफ़र बनाने के लिए ${\sqrt {A}}$ अद्वितीय मान नहीं होते हैं, तो सामान्य रूप से उप-इष्टतम इन-प्लेस मर्ज संचालन किया जाता है जहां यह बार-बार बाइनरी खोज करता है और A को B में घुमाता है। यद्यपि, किसी भी उपसरणी के भीतर अद्वितीय मानों की ज्ञात कमी संख्या पर जटिल सीमा लगाती है बाइनरी खोज और घूर्णन जो इस चरण के समय किए जाएंगे, जो कि फिर से ${\sqrt {A}}$ वस्तुओं को ${\sqrt {A}}$ समय, या $O(n)$ तक घुमाया जाता है। इस प्रकार से प्रत्येक ब्लॉक का आकार भी उस स्थिति में छोटा करने के लिए समायोजित किया जाता है जहां उसे ${\sqrt {A}}$ मान मिलते हैं परन्तु 2 ${\sqrt {A}}$ नहीं, जो किसी भी A या B ब्लॉक में निहित अद्वितीय मानों की संख्या को और सीमित कर देता है।

अतः A ब्लॉक को टैग करना प्रत्येक A उपसरणी के लिए ${\sqrt {A}}$ बार किया जाता है, फिर A ब्लॉक को रोल किया जाता है और B ब्लॉक में ${\sqrt {A}}$ बार तक डाला जाता है। स्थानीय मर्ज मानक मर्ज की समान $O(n)$ जटिलता को बनाए रखते हैं, यद्यपि अधिक असाइनमेंट के साथ क्योंकि मानों को अनुकरण करने के अतिरिक्त स्वैप किया जाना चाहिए। नवीन न्यूनतम A ब्लॉक को खोजने के लिए रैखिक खोज ${\sqrt {A}}$ ब्लॉक ${\sqrt {A}}$ बार दोहराई जाती है। और बफ़र पुनर्वितरण प्रक्रिया बफ़र निष्कर्षण के समान है परन्तु विपरीत है, और इसलिए इसमें समान $O(n)$ जटिलता है।

इस प्रकार से उच्चतम जटिलता को छोड़कर सभी को छोड़ने और यह विचार करने के बाद कि बाहरी मर्ज लूप में $\log {n}$ स्तर हैं, इससे सबसे निकृष्ट और औसत स्थितियों के लिए $O(n\log {n})$ की अंतिम स्पर्शोन्मुख जटिलता हो जाती है। अतः सर्वोत्तम स्थिति के लिए, जहां डेटा पहले से ही क्रम में है, मर्ज चरण पहले स्तर के लिए $n/16$ तुलना करता है, फिर $n/32$ , $n/64$ , $n/128$ , आदि। यह एक प्रसिद्ध गणितीय श्रृंखला है जो $O(n)$ को हल करती है।

मेमोरी

चूंकि ब्लॉक सॉर्ट पुनरावर्तन (कंप्यूटर विज्ञान) है और इसमें मेमोरी प्रबंधन मैन्युअल मेमोरी प्रबंधन के उपयोग की आवश्यकता नहीं होती है, इससे निरंतर स्टैक (अमूर्त डेटा प्रकार) और हीप स्थान होता है। इस प्रकार से यह ट्रांसडिकोटोमस मॉडल में O(1) सहायक मेमोरी का उपयोग करता है, जो स्वीकार करता है कि A और B के लिए रेंज का ट्रैक रखने के लिए आवश्यक O(log n) बिट 32-बिट या 64-बिट पर 32 या 64 से अधिक नहीं हो सकते हैं। अतः कंप्यूटिंग प्रणाली, क्रमशः, और इसलिए किसी भी सरणी के लिए O(1) स्थान को सरल बनाता है जिसे संभवतः आवंटित किया जा सकता है।

स्थिरता

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

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

इस प्रकार से A ब्लॉक को B ब्लॉक के माध्यम से रोल करने से पहले, प्रत्येक A ब्लॉक का दूसरा मान पहले बफर के मान के साथ परिवर्तित कर दिया जाता है। उस समय A ब्लॉक B ब्लॉक से गुजरने के क्रम से बाहर चले जाते हैं। यद्यपि, बार जब उसे पता चल जाता है कि उसे सबसे छोटे A ब्लॉक को पूर्व B ब्लॉक में कहाँ सम्मिलित करना चाहिए, तो उस सबसे छोटे A ब्लॉक को A ब्लॉक के प्रारंभ में वापस ले जाया जाता है और उसका दूसरा मान पुनः स्थापित कर दिया जाता है। जब तक सभी A ब्लॉक डाले जाएंगे, A ब्लॉक फिर से क्रम में होंगे और पहले बफर में मूल क्रम में इसके मूल मान सम्मिलित होंगे।

इस प्रकार से A ब्लॉक को कुछ B मानों के साथ मर्ज करते समय दूसरे बफ़र को स्वैप स्थान के रूप में उपयोग करने से उस बफ़र की विवरण को पुनर्व्यवस्थित किया जाता है। यद्यपि, जैसा कि एल्गोरिदम ने पहले ही सुनिश्चित कर लिया है कि बफ़र में मात्र अद्वितीय मान हैं, बफ़र की विवरण को सॉर्ट करना उनके मूल स्थिर क्रम को पुनर्स्थापित करने के लिए पर्याप्त है।

अनुकूलता

अतः ब्लॉक सॉर्ट दो स्तरों पर अनुकूली सॉर्ट है: सबसे पहले, यह A और B उपसरणी को मर्ज करना छोड़ देता है जो पहले से ही क्रम में हैं। इसके बाद, जब A और B को मर्ज करने की आवश्यकता होती है और उन्हें समान आकार के ब्लॉक में तोड़ दिया जाता है, तो A ब्लॉक को मात्र B के माध्यम से रोल किया जाता है, जहां तक आवश्यक होता है, और प्रत्येक ब्लॉक को मात्र इसके तुरंत बाद B मानों के साथ मर्ज कर दिया जाता है। इस प्रकार से मूल रूप से डेटा जितना अधिक व्यवस्थित होगा, B मान उतने ही कम होंगे जिन्हें A में मर्ज करने की आवश्यकता होगी।

लाभ

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

हानि

इस प्रकार से ब्लॉक सॉर्ट डेटा की सॉर्ट की गई श्रेणियों का उतने ठीक स्तर पर शोषण नहीं करता है जितना कि कुछ अन्य एल्गोरिदम, जैसे कि टिमसॉर्ट।^[14] यह मात्र दो पूर्वनिर्धारित स्तरों पर इन क्रमबद्ध श्रेणियों की जाँच करता है: A और B उपसरणी, और A और B ब्लॉक। अतः मर्ज सॉर्ट की तुलना में इसे लागू करना और समानांतर बनाना भी जटिल है।

संदर्भ

↑ ^1.0 ^1.1 Kutzner, Arne; Kim, Pok-Son (2008). अनुपात आधारित स्थिर इन-प्लेस विलय (PDF). Lecture Notes in Computer Science. Vol. 4978. Springer Berlin Heidelberg. pp. 246–257. Retrieved 2016-09-07.
↑ Mannila, Heikki; Ukkonen, Esko (14 May 1984). "इन-सीटू विलय के लिए एक सरल रैखिक समय एल्गोरिदम". Information Processing Letters. 18 (4): 203–208. doi:10.1016/0020-0190(84)90112-1.
↑ Kronrod, M. Alexander (February 1969). "Оптимальный алгоритм упорядочения без рабочего поля" [An Optimal Ordering Algorithm without a Field of Operation]. Proceedings of the USSR Academy of Sciences (in русский). 186 (6): 1256–1258.
↑ Bentley, Jon (2006). प्रोग्रामिंग मोती (2nd ed.).
↑ Warren Jr., Henry S. (2013) [2002]. हैकर की प्रसन्नता (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
↑ Pardo, Luis Trabb (1977). इष्टतम स्थान और समय सीमा के साथ स्थिर छँटाई और विलय. SIAM Journal on Computing. Vol. 6. pp. 351–372.
↑ ^7.0 ^7.1 Geffert, Viliam; Katajainen, Jykri; Pasanen, Tomi (April 2000). "असम्बद्ध रूप से कुशल इन-प्लेस विलय". Theoretical Computer Science. 237 (1–2): 159–181. CiteSeerX 10.1.1.22.5750. doi:10.1016/S0304-3975(98)00162-5.
↑ Hwang, F. K.; Lin, S. (1972). दो असंयुक्त रैखिक क्रमित सेटों को मर्ज करने के लिए एक सरल एल्गोरिदम. SIAM Journal on Computing. Vol. 1. pp. 31–39. doi:10.1137/0201004. ISSN 0097-5397.
↑ Dudzinski, Krzysztof; Dydek, Andrzej (1981). एक स्थिर भंडारण विलय एल्गोरिदम पर. Information Processing Letters. Vol. 12. pp. 5–8.
↑ Symvonis, Antonios (1995). "इष्टतम स्थिर विलय". The Computer Journal. 38 (8): 681–690. CiteSeerX 10.1.1.55.6058. doi:10.1093/comjnl/38.8.681.
↑ Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2014-04-15. Retrieved 2014-03-23.
↑ Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2016-12-20. Retrieved 2016-12-11.
↑ "C, C++ और Java के लिए ब्लॉक सॉर्ट का सार्वजनिक डोमेन कार्यान्वयन". GitHub. Retrieved 2014-03-23.
↑ Tim Peters. "Re: WikiSort". Retrieved 2020-09-13.

[kim2008-1] 1.0 ^1.1 Kutzner, Arne; Kim, Pok-Son (2008). अनुपात आधारित स्थिर इन-प्लेस विलय (PDF). Lecture Notes in Computer Science. Vol. 4978. Springer Berlin Heidelberg. pp. 246–257. Retrieved 2016-09-07.

[mannilla-2] Mannila, Heikki; Ukkonen, Esko (14 May 1984). "इन-सीटू विलय के लिए एक सरल रैखिक समय एल्गोरिदम". Information Processing Letters. 18 (4): 203–208. doi:10.1016/0020-0190(84)90112-1.

[kronrod-3] Kronrod, M. Alexander (February 1969). "Оптимальный алгоритм упорядочения без рабочего поля" [An Optimal Ordering Algorithm without a Field of Operation]. Proceedings of the USSR Academy of Sciences (in русский). 186 (6): 1256–1258.

[4] Bentley, Jon (2006). प्रोग्रामिंग मोती (2nd ed.).

[Warren_2013-5] Warren Jr., Henry S. (2013) [2002]. हैकर की प्रसन्नता (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.

[pardo-6] Pardo, Luis Trabb (1977). इष्टतम स्थान और समय सीमा के साथ स्थिर छँटाई और विलय. SIAM Journal on Computing. Vol. 6. pp. 351–372.

[geffert-7] 7.0 ^7.1 Geffert, Viliam; Katajainen, Jykri; Pasanen, Tomi (April 2000). "असम्बद्ध रूप से कुशल इन-प्लेस विलय". Theoretical Computer Science. 237 (1–2): 159–181. CiteSeerX 10.1.1.22.5750. doi:10.1016/S0304-3975(98)00162-5.

[8] Hwang, F. K.; Lin, S. (1972). दो असंयुक्त रैखिक क्रमित सेटों को मर्ज करने के लिए एक सरल एल्गोरिदम. SIAM Journal on Computing. Vol. 1. pp. 31–39. doi:10.1137/0201004. ISSN 0097-5397.

[dydek-9] Dudzinski, Krzysztof; Dydek, Andrzej (1981). एक स्थिर भंडारण विलय एल्गोरिदम पर. Information Processing Letters. Vol. 12. pp. 5–8.

[symvonis-10] Symvonis, Antonios (1995). "इष्टतम स्थिर विलय". The Computer Journal. 38 (8): 681–690. CiteSeerX 10.1.1.55.6058. doi:10.1093/comjnl/38.8.681.

[implementation-11] Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2014-04-15. Retrieved 2014-03-23.

[download-12] Arne Kutzner. "इन-प्लेस मर्जिंग एल्गोरिथम बेंचमार्किंग टूल". Archived from the original on 2016-12-20. Retrieved 2016-12-11.

[wikisort-13] "C, C++ और Java के लिए ब्लॉक सॉर्ट का सार्वजनिक डोमेन कार्यान्वयन". GitHub. Retrieved 2014-03-23.

[tim-14] Tim Peters. "Re: WikiSort". Retrieved 2020-09-13.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

ब्लॉक सॉर्ट

Namespaces

More

Page actions

Contents

अवलोकन

एल्गोरिथम

बाह्य पाश

बफ़र निष्कर्ष

टैग A ब्लॉक

रोल और ड्राप

स्थानीय मर्ज

पुनर्वितरित

प्रकार

विश्लेषण

जटिलता

मेमोरी

स्थिरता

अनुकूलता

लाभ

हानि

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ब्लॉक सॉर्ट

अवलोकन

एल्गोरिथम

बाह्य पाश

बफ़र निष्कर्ष

टैग A ब्लॉक

रोल और ड्राप

स्थानीय मर्ज

पुनर्वितरित

प्रकार

विश्लेषण

जटिलता

मेमोरी

स्थिरता

अनुकूलता

लाभ

हानि

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories