Come si scrive iterativamente l'unisci sort?

Question

Ho scritto una versione ricorsiva di merge sort. Si avvale di un merge di routine separata:

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

per risparmiare spazio di stack (e per i calci/la pura gioia di algoritmi di apprendimento), sto cercando di scrivere questa funzione in modo iterativo. Tuttavia, trovo questo difficile perché non sono sicuro di come combinare liste disparate alla fine.

Grazie!

Answer 1

Avrete bisogno di una funzione merge (la stessa o quasi la stessa funzione merge) che verrà chiamata più volte. Pertanto, non è necessario modificare la funzione merge.

Questa è una soluzione a più passaggi. Inizia con una dimensione del blocco pari a 2 e raddoppia la dimensione del blocco in ogni passaggio.

In ogni passaggio, dividere l'elenco in blocchi non sovrapposti di qualsiasi dimensione. Dividi ogni pezzo in 2 e chiama merge sulle 2 parti.

Questa è una versione bottom-up.

Answer 2

Espansione basata sulla descrizione di Divya (aggiunta anche una funzione di test per la verifica). Il codice seguente può essere ottimizzato eliminando i sotto-array (data_1 e data_2) e l'ordinamento in atto.

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

Ecco Java Attuazione

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

Ecco la prova di unità

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

ricorsione è più intuitivo da cui io preferisco lo stesso, tranne in alcune situazioni quando voglio evitare una profondità dello stack significativa (ad es. durante il consumo di determinate implementazioni di co-routine). In caso di Merge sort comunque la versione iterativa è in realtà più facile da seguire (almeno lo pseudo codice).

Tutto ciò che serve è un ciclo nidificato con il ciclo interno che esegue l'unione su coppie di elementi 2^k con il ciclo esterno responsabile dell'incremento di k.

Un ulteriore passaggio necessario è quello di unire qualsiasi gruppo non abbinato con il gruppo unito precedente. Un gruppo non abbinato si incontrerà se il numero di elementi non è un potere di 2. Un gruppo non abbinato sarà sempre alla fine dell'iterazione.

ad es. [5, 7, 3, 4, 1, 9] -> [5, 7] [3, 4] [1, 9] -> [3, 4, 5, 7] [1, 9] -> [ 1, 3, 4, 5, 7, 9]

Nell'esempio precedente [1, 9] è un gruppo che non aveva un altro gruppo da unire inizialmente. Così è stato fuso con il gruppo precedente (che si era fusa e ordinati già)

Ecco un'implementazione pitone:

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 

ho usato la funzione di fusione dalla versione normale (ricorsiva). Mentre il codice sopra non è il più elegante, ma funziona e ha la stessa complessità della versione ricorsiva.(Non ho controllato a fondo, ma sembra così a me da una rapida occhiata)

Ecco una prova di unità:

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