बैचर का मर्ज-एक्सचेंज सॉर्ट करें

Question

क्या किसी के पास बैचर के मर्ज-एक्सचेंज सॉर्ट की अच्छी मार्गदर्शिका/स्पष्टीकरण है?

यह बैचर के बिटोनिक सॉर्ट या बैचर के अजीब-यहां तक ​​कि मर्ज सॉर्ट के समान एल्गोरिदम नहीं है, हालांकि कई लेख बताते हैं कि यह है।

Answer 1

डोनाल्ड Knuth, कंप्यूटर प्रोग्रामिंग की कला, एल्गोरिदम 5.2.2 एम (वॉल्यूम III, पृष्ठ 111)।

केन बैचर (1 9 68), "Sorting networks and their application", प्रो। AFIPS स्प्रिंग संयुक्त कंप्यूटर सम्मेलन 32: 307-314।

Answer 2

से http://www.eli.sdsu.edu/courses/spring96/cs662/notes/batcher/batcher.html

Input: N and array A[1:N] of items to sort 

set T = Ceiling(lg(N)) 

for P = 2T-1, 2T-2, 2T-3, ..., 1 do 
R = 0, D = P 
for Q = 2T-1, 2T-2, 2T-3, ..., P do 
for (K = 1 to N - D) and ((K-1) P) = R do in parallel 
if A[K] > A[K + D] then 
swap(A[K], A[K + D ]) 
end if 
end for 
D = Q - P 
R = P 
end for 
end for 


(K + 1) P means logical and of K and P 

If number of processors is less than N than the swap becomes a merge 

This site इस एल्गोरिथ्म के एक दृश्य है

Answer 3

सरल कार्यान्वयन :)

int FloorLog2(int value) 
{ 
    int result = -1; 
    for (int i = 1; i < value; i <<= 1, ++result); 
    return result; 
} 

void BatcherSort(int* array, int length) 
{ 
    int t = FloorLog2(length); 
    int p0 = (1 << t); 
    int p = p0; 

    do 
    { 
     int q = p0; 
     int r = 0; 
     int d = p; 

     while (r == 0 || q != p) 
     { 
      if (r != 0) 
      { 
       d = q - p; 
       q >>= 1; 
      } 

      for (int i = 0; i < length - d; ++i) 
      { 
       if (((i & p) == r) && array[i] > array[i + d]) 
       { 
        int swap = array[i]; 
        array[i] = array[i + d]; 
        array[i + d] = swap; 
       } 
      } 

      r = p; 
     } 

     p >>= 1; 
    } 
    while (p > 0); 
}