どのように反復的にマージソートを書いていますか？

Question

私は、マージソートの再帰的なバージョンを書いています。

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:])) 

は、スタック領域を節約するために（そしてキックのために/学習アルゴリズムの純粋な喜び）、私は、反復的に、この関数を記述しようとしています：それは別のmergeルーチンを使用しています。しかし、私は最後に別のリストをどのように組み合わせるのか分からないので、これは困難です。

ありがとうございました！

Answer 1

繰り返し呼び出されるmerge関数（同じまたはほぼ同じmerge関数）が必要です。したがって、merge機能を変更する必要はありません。

これは複数回の解決策です。チャンクサイズは2で始まり、すべてのパスでチャンクサイズを2倍にします。

各パスで、リストを重複しないサイズのチャンクに分割します。すべてのチャンクを2つに分割し、2つの部分でmergeを呼び出します。

これはボトムアップバージョンです。

Answer 2

私はDivyaの記述に基づいて拡張しました（検証のためのテスト関数も追加されました）。以下のコードは、サブ配列（data_1とdata_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

ここでJava実装

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

再帰が故に、より直感的です（例えば、特定の共同ルーチンの実装を消費している間）。しかし、マージソートの場合、反復バージョンは実際に従う方が簡単です（少なくとも疑似コード）。

必要なのは、内側ループが2^k要素のペアに対してマージを実行し、外側ループがkをインクリメントする役割を果たすことです。

追加の手順は、すべてのペアのないグループを以前の結合されたグループとマージすることです。要素の数が2の累乗でない場合、ペアのないグループが発生します。ペアのないグループは常に反復の最後になります。

〔5,7,3,4,1,9〕→〔5,7〕〔3,4〕〔1,9〕→〔3,4,5,7〕〔1,9〕→〔5,7,3,4,1,9〕→〔5,7,3,4,1,9〕→〔5,7〕〔3,4〕〔1,9〕上記の例で[1,9]は、最初にマージされる別のグループを持たないグループです。したがって、それがここで（合併とすでにソートされていた）前のグループ

と合併したPython実装です：

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