एक व्यक्ति कैसे विलय प्रकार लिखता है?

Question

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

def merge(lst1, lst2): 
    i = j = 0 
    merged = [] 
    while i < len(lst1) and j < len(lst2): 
     if lst1[i] <= lst2[j]: 
      merged.append(lst1[i]) 
      i += 1 
     else: 
      merged.append(lst2[j]) 
      j += 1 
    merged.extend(lst1[i:]) 
    merged.extend(lst2[j:]) 
    return merged 

def merge_sort(lst): 
    if len(lst) < 2: 
     return lst 
    else: 
     middle = len(lst)/2 
     return merge(merge_sort(lst[:middle]), merge_sort(lst[middle:])) 

ढेर अंतरिक्ष के संरक्षण के लिए (और किक के लिए/सीखने वाले एल्गोरिदम की सरासर खुशी), मैं एक सतत तरीके से इस समारोह लिखने के लिए कोशिश कर रहा हूँ। हालांकि, मुझे यह मुश्किल लगता है क्योंकि मुझे यकीन नहीं है कि अंत में अलग-अलग सूचियों को कैसे जोड़ना है।

धन्यवाद!

Answer 1

आपको merge फ़ंक्शन (समान या लगभग merge फ़ंक्शन) की आवश्यकता होगी जिसे बार-बार कहा जाएगा। इसलिए, आपको merge फ़ंक्शन को बदलने की आवश्यकता नहीं है।

यह एक एकाधिक पास समाधान है। 2 के एक खंड आकार के साथ शुरू करें और प्रत्येक पास में खंड आकार को दोगुना करें।

प्रत्येक पास में, सूची को आकार के गैर-ओवरलैपिंग हिस्सों में विभाजित करें। प्रत्येक भाग को 2 में विभाजित करें और 2 भागों पर merge पर कॉल करें।

यह एक निचला संस्करण है।

Answer 2

मैंने दिव्य के विवरण के आधार पर विस्तार किया (सत्यापन के लिए एक परीक्षण समारोह भी जोड़ा)। उप-सरणी (डेटा_1 और डेटा_2) को हटाकर और क्रमबद्ध क्रमबद्ध करके नीचे दिए गए कोड को अनुकूलित किया जा सकता है।

def merge_sort_iterative(data): 
    """ gets the data using merge sort and returns sorted.""" 

    for j in range(1, len(data)): 
    j *= 2 
    for i in range(0,len(data),j): 
     data_1 = data[i:i+(j/2)] 
     data_2 = data[i+(j/2):j-i] 
     l = m = 0 
     while l < len(data_1) and m < len(data_2): 
     if data_1[l] < data_2[m]: 
      m += 1 
     elif data_1[l] > data_2[m]: 
      data_1[l], data_2[m] = data_2[m], data_1[l] 
      l += 1 
     data[i:i+(j/2)], data[i+(j/2):j-i] = data_1, data_2 

    return data 

def test_merge_sort(): 
    """test function for verifying algorithm correctness""" 

    import random 
    import time 

    sample_size = 5000 
    sample_data = random.sample(range(sample_size*5), sample_size) 
    print 'Sample size: ', sample_size 

    begin = time.time() 
    sample_data = [5,4,3,2,1] 
    result = merge_sort_iterative(sample_data) 
    end = time.time() 
    expected = sorted(sample_data) 
    print 'Sorting time: %f \'secs'%(end-begin) 

    assert result == expected, 'Algorithm failed' 
    print 'Algorithm correct' 

if __name__ == '__main__': 
    test_merge_sort() 

Answer 3

यहाँ जावा कार्यान्वयन

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) { 

    for (int i = 1; i <seed.length; i=i+i) 
    { 
     for (int j = 0; j < seed.length - i; j = j + i+i) 
     { 
      inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1)); 
     } 
    }  
} 

public static <T extends Comparable<? super T>> void inPlaceMerge(T[] collection, int low, int mid, int high) { 
    int left = low; 
    int right = mid + 1; 

    if(collection[mid].equals(collection[right])) { 
     return ;//Skip the merge if required 
    } 
    while (left <= mid && right <= high) {   
     // Select from left: no change, just advance left 
     if (collection[left].compareTo(collection[right]) <= 0) { 
      left ++; 
     } else { // Select from right: rotate [left..right] and correct 
      T tmp = collection[right]; // Will move to [left] 
      rotateRight(collection, left, right - left); 
      collection[left] = tmp; 
      // EVERYTHING has moved up by one 
      left ++; right ++; mid ++; 
     } 
    }  
} 

है यहाँ इकाई परीक्षण है

private Integer[] seed; 

@Before 
public void doBeforeEachTestCase() { 
    this.seed = new Integer[]{4,2,3,1,5,8,7,6}; 
} 
@Test 
public void iterativeMergeSortFirstTest() { 
    ArrayUtils.<Integer>iterativeMergeSort(seed); 
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8}; 
    assertThat(seed, equalTo(result)); 
} 

Answer 4

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

यह आवश्यक है कि आंतरिक लूप के साथ घोंसला वाला लूप 2^के तत्वों के जोड़े पर विलय कर रहा है जिसमें बाहरी लूप को बढ़ाने के लिए ज़िम्मेदार है।

एक अतिरिक्त चरण जो आवश्यक है, पिछले विलय वाले समूह के साथ किसी भी unpaired समूह को मर्ज करना है। यदि तत्वों की संख्या 2 की शक्ति नहीं है तो एक unpaired समूह का सामना किया जाएगा। एक unpaired समूह हमेशा पुनरावृत्ति के अंत में होगा।

उदा। [5, 7, 3, 4, 1, 9] -> [5, 7] [3, 4] [1, 9] -> [3, 4, 5, 7] [1, 9] -> [ 1, 3, 4, 5, 7, 9]

उपरोक्त उदाहरण में [1, 9] एक समूह है जिसमें प्रारंभिक रूप से विलय करने वाला कोई अन्य समूह नहीं था। इस प्रकार यह पिछले समूह (जो विलय कर दिया गया था और पहले से ही क्रमबद्ध)

यहाँ एक अजगर कार्यान्वयन है साथ विलय कर दिया गया था:

from MergeSort import merge 

def sort(arr): 
    n = len(arr) - 1 
    c = 1 
    start = 0 
    mid = 0 
    end = 0 
    while c <= n: 
     while end < n: 
      mid = start + c//2 
      end = start + c 
      if (start < n) and (end <= n): 
       merge(arr, start, mid, end) 
       start = end + 1 
      else: 
       merge(arr, start - c - 1, start-1, n) 
     c = 2*c + 1 
     start = 0 
     mid = 0 
     end = 0 

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

यहाँ एक इकाई परीक्षण है:

def test_merge_sort_iterative(self): 
    for i in range(1, 100): 
     length = randint(10, 5000) 
     data = [randint(1, 10000) for x in range(1, length)] 
     IterativeMergeSort.sort(data) 
     issorted = True 
     i = 0 
     while (i < len(data) - 1) & issorted: 
      if data[i] > data[i + 1]: 
       issorted = False 
      i += 1 
    self.assertTrue(issorted, data) 
    return