Làm thế nào để một cách lặp lại sắp xếp hợp nhất?

Question

Tôi đã viết phiên bản đệ quy của sắp xếp hợp nhất. Nó làm cho việc sử dụng một merge thói quen riêng biệt:

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

Bảo tồn không gian ngăn xếp (và cho đá/niềm vui tuyệt đối của thuật toán học), tôi đang cố gắng để viết chức năng này một cách lặp đi lặp lại. Tuy nhiên, tôi thấy điều này khó khăn vì tôi không chắc chắn làm thế nào để kết hợp các danh sách khác nhau vào cuối cùng.

Cảm ơn bạn!

Answer 1

Bạn sẽ cần chức năng merge (chức năng tương tự hoặc gần như giống nhau merge) sẽ được gọi nhiều lần. Vì vậy, bạn không cần phải thay đổi chức năng merge.

Đây là giải pháp nhiều lần. Bắt đầu với một kích thước chunk của 2 và tăng gấp đôi kích thước chunk trong mỗi pass.

Trong mỗi lần vượt qua, hãy phân đoạn danh sách thành các phần không chồng chéo có kích thước bất kỳ. Chia từng đoạn thành 2 và gọi merge trên 2 phần.

Đây là phiên bản từ dưới lên.

Answer 2

Tôi mở rộng dựa trên mô tả của Divya (cũng đã thêm chức năng kiểm tra để xác minh). Mã dưới đây có thể được tối ưu hóa bằng cách loại bỏ các mảng phụ (dữ liệu_1 và dữ liệu_2) và sắp xếp tại chỗ.

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

Đây là Java thực hiện

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 ++; 
     } 
    }  
} 

Đây là bài kiểm tra đơn vị

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

Đệ quy là trực quan hơn vì thế tôi thích giống nhau, ngoại trừ trong một số trường hợp khi tôi muốn tránh một độ sâu ngăn xếp đáng kể (ví dụ: trong khi tiêu thụ một số triển khai đồng nhất định). Trong trường hợp Merge sắp xếp, tuy nhiên phiên bản lặp lại thực sự dễ theo dõi hơn (ít nhất là mã giả).

Tất cả những gì cần thiết là một vòng lặp lồng nhau với vòng lặp bên trong thực hiện các lần hợp nhất trên các cặp phần tử 2^k với vòng lặp bên ngoài chịu trách nhiệm tăng dần k.

Một bước bổ sung cần thiết là hợp nhất bất kỳ nhóm chưa được ghép nối nào với nhóm đã hợp nhất trước đó. Một nhóm chưa được ghép nối sẽ gặp phải nếu số phần tử không phải là một sức mạnh của 2. Một nhóm chưa được ghép nối sẽ luôn ở cuối của lần lặp.

ví dụ: [5, 7, 3, 4, 1, 9] -> [5, 7] [3, 4] [1, 9] -> [3, 4, 5, 7] [1, 9] -> [ 1, 3, 4, 5, 7, 9]

Trong ví dụ trên [1, 9] là một nhóm không có nhóm khác được hợp nhất với ban đầu. Do đó nó được sáp nhập với nhóm trước đó (mà đã được sáp nhập và sắp xếp đã được)

Đây là một thực hiện 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 

tôi đã sử dụng chức năng merge từ (recursive) phiên bản thông thường. Trong khi mã trên không phải là thanh lịch nhất, nhưng nó hoạt động và có độ phức tạp tương tự như phiên bản đệ quy.(Tôi đã không kiểm tra kỹ lưỡng nhưng có vẻ như vậy để tôi khỏi trong nháy mắt nhanh)

Dưới đây là một thử nghiệm đơn vị:

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