¿Cómo implementar una ordenación por fusión de listas?

Responder
Irenicus
Mensajes: 1238
Registrado: 19 Mar 2007 23:22

¿Cómo implementar una ordenación por fusión de listas?

Mensaje por Irenicus »

¡Buenas!

Me gustaría implementar mi propia ordenación por fusión (merge sort) de listas. Sé cómo hacerlo con arrays y vectores, pero he de usar la librería estándar de C++ de list. En http://www.cplusplus.com/reference/stl/list/ no he sabido encontrarlo.

Si implemento mi propia lista, con nodos y punteros al siguiente sé cómo hacerlo, pero no sé cómo funciona en la librería de C++.

Código: Seleccionar todo

list<my_clase> fusionar(list<my_clase> L1, list<my_clase> L2) {

    if (L1.empty()) return L2;
    if (L2.empty()) return L1;
    
    list<my_clase>::iterator it1 = L1.begin();
    list<my_clase>::iterator it2 = L2.begin();
    if (*it1 <= *it2) {
       L1 -> siguiente = fusionar(L1 -> siguiente, L2)
       return L1;
      };
    else {
          L2 -> siguiente = fusionar(L1, L2 -> siguiente);
          return L2;
    }
    
}

void dividir(list<my_clase>& L1, list<my_clase>& L2, int m){
    list<my_clase>::iterator it = L1.begin();
    while (m > 1) {
        ++it;
        --m;
    };
    L2 = it    "-> siguiente", para que nos entendamos.
    it  "-> siguiente" = NULL;

}

void mergesort (list<my_clase>& lista, int n) {
    if (n <= 1) return;
    int m = n / 2;
    list<my_clase> aux = NULL;
    dividir(lista, aux, m);
    
    mergesort(L, m);
    mergesort(aux, n - m);
    
    lista = fusionar(lista, aux);
}
Responder