¿Cómo se escribe iterativamente el tipo de combinación?

Question

He escrito una versión recursiva del tipo de fusión. Se hace uso de una rutina separada 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:])) 

para conservar espacio de pila (y por diversión/el simple placer de algoritmos de aprendizaje), estoy tratando de escribir esta función de manera iterativa. Sin embargo, esto me resulta difícil porque no estoy seguro de cómo combinar listas dispares al final.

¡Gracias!

Answer 1

Necesitará una función merge (la misma o casi la misma función merge) a la que se llamará repetidamente. Por lo tanto, no necesita cambiar la función merge.

Esta es una solución de pase múltiple. Comience con un tamaño de fragmento de 2 y duplique el tamaño del fragmento en cada pasada.

En cada pasada, particione la lista en trozos de tamaño no superpuestos. Divida cada porción en 2 y llame al merge en las 2 partes.

Esta es una versión ascendente.

Answer 2

Expandí en base a la descripción de Divya (también se agregó una función de prueba para verificación). El siguiente código se puede optimizar eliminando sub-arrays (data_1 y data_2) y clasificando en su lugar.

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

Aquí es Java Implementació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 ++; 
     } 
    }  
} 

Aquí está la prueba de la unidad

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

La recursividad es más intuitivo, por lo tanto prefiero el mismo, excepto en algunas situaciones en las que quiero evitar una profundidad significativa de la pila (por ejemplo, mientras se consumen ciertas implementaciones de co-rutina). Sin embargo, en el caso de Merge sort, la versión iterativa es realmente más fácil de seguir (al menos el pseudo código).

Todo lo que se necesita es un bucle anidado con el bucle interno realizando fusiones en pares de 2^k elementos con el bucle externo responsable de incrementar k.

Un paso adicional que se requiere es unir cualquier grupo no emparejado con el grupo fusionado anterior. Se encontrará un grupo desapareado si la cantidad de elementos no es una potencia de 2. Un grupo no emparejado siempre estará al final de la iteración.

p. Ej. [5, 7, 3, 4, 1, 9] -> [5, 7] [3, 4] [1, 9] -> [3, 4, 5, 7] [1, 9] -> [ 1, 3, 4, 5, 7, 9]

En el ejemplo anterior [1, 9] hay un grupo que no tenía otro grupo para fusionarse inicialmente. Por lo tanto, se fusionó con el grupo anterior (que se había fusionado y ya ordenados)

Aquí es una implementación de 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 

he utilizado la función de combinación de la versión normal (recursivo). Si bien el código anterior no es el más elegante, pero funciona y tiene la misma complejidad que la versión recursiva.(No he comprobado a fondo, pero parece por lo que a mí de un vistazo rápido)

Aquí es una prueba de unidad:

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