Jak iteracyjnie pisać sortowanie scalone?

Question

Napisałem rekursywną wersję sortowania scalonego. To sprawia, że ​​korzystanie z osobnym merge rutyny:

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

celu zaoszczędzenia miejsca stosu (i kopnięć/sama radość algorytmów uczenia), staram się napisać tę funkcję w sposób iteracyjny. Jednak uważam to za trudne, ponieważ nie jestem pewien, jak połączyć różne listy na samym końcu.

Dziękujemy!

Answer 1

Będziesz potrzebować funkcji merge (tej samej lub prawie tej samej funkcji merge), która będzie wywoływana wielokrotnie. Nie musisz więc zmieniać funkcji merge.

To rozwiązanie wieloprzepływowe. Rozpocznij od wielkości kawałka 2 i dwukrotnie wielkości porcji w każdym przebiegu.

W każdym przejściu podziel listę na niepokrywające się fragmenty o dowolnym rozmiarze. Podziel każdą porcję na 2 i zadzwoń merge na 2 części.

To jest oddolna wersja.

Answer 2

Zostałem rozwinięty w oparciu o opis Divyi (dodano również funkcję testową do weryfikacji). Poniższy kod można zoptymalizować, eliminując podparki (data_1 i dane_2) i sortując w miejscu.

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

Oto Java Realizacja

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

Oto testów jednostkowych

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

Rekurencja jest bardziej intuicyjne stąd wolę takie same z wyjątkiem niektórych sytuacjach, kiedy chcemy uniknąć znacząca głębokość stosu (np. podczas konsumowania pewnych implementacji rutynowych). W przypadku sortowania Merge iteratywna wersja jest jednak łatwiejsza do śledzenia (przynajmniej pseudo kod).

Wszystko, co jest potrzebne, to zagnieżdżona pętla z wykonaniem wewnętrznej pętli scala na pary 2^k elementów z zewnętrzną pętlą odpowiedzialną za inkrementację k.

Dodatkowym krokiem, który jest wymagany, jest scalenie niesparowanej grupy z poprzednią scaloną grupą. Niesparowana grupa zostanie napotkana, jeśli liczba elementów nie jest potęgą 2. Niesparowana grupa zawsze znajdzie się na końcu iteracji.

np. [5, 7, 3, 4, 1, 9] -> [5, 7] [3, 4] [1, 9] -> [3, 4, 5, 7] [1, 9] -> [ 1,3,4,5, 7,9). W ten sposób została połączona z poprzedniej grupy (które zostały połączone i sortowanych już)

Oto implementacja Pythona:

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 

użyłem funkcji scalania od zwykłego (rekurencyjne) wersji. Chociaż powyższy kod nie jest najbardziej elegancki, ale działa i ma taką samą złożoność, jak wersja rekursywna.(Ja dokładnie nie sprawdził, ale wydaje się tak do mnie z szybkim spojrzeniem)

Tutaj jest test jednostki:

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