Tema: Ordenacion de lista de objetos
Ver Mensaje Individual
  #12 (permalink)  
Antiguo 13/05/2011, 16:04
alexg88
 
Fecha de Ingreso: abril-2011
Mensajes: 1.342
Antigüedad: 13 años
Puntos: 344
Respuesta: Ordenacion de lista de objetos
Basándome en el código proporcionado por sam90 voy a poner un intento de ordenación mediante Quicksort.

Código C++: 
Ver original
  1. /*    CLASE NODOLIBRO  */
  2. class NodoLibro
  3. {
  4. public:
  5.     libro * lib;
  6.     NodoLibro * anterior;
  7.     NodoLibro * siguiente;
  8.     NodoLibro(libro * l)
  9.     {
  10.         lib = l;
  11.         anterior = NULL;
  12.         siguiente = NULL;
  13.     }
  14.     bool compare(const NodoLibro * l)
  15.     {
  16.         if (lib->codigo > l->lib->codigo)
  17.             return true;
  18.         return false;
  19.     }
  20.     
  21.     void changeLibro(NodoLibro * l)
  22.     {
  23.         libro * temp = lib;
  24.         lib = l->lib;
  25.         l->lib =temp;
  26.     }
  27. };
  28.  
  29. /*    CLASE LISTA  */
  30.  
  31. class Lista
  32. {
  33.  
  34. private:
  35.     NodoLibro * primero;
  36.     NodoLibro * ultimo;
  37.     int distancia(NodoLibro *first, NodoLibro *last){
  38.  
  39.         int i=1;
  40.  
  41.         NodoLibro *ptr = first;
  42.  
  43.         while (ptr != last)
  44.          {
  45.           ptr = ptr->siguiente;
  46.           i++;
  47.          }
  48.  
  49.      return i;
  50.  
  51.     }
  52.  
  53.     void QuicksortAux(NodoLibro *first,NodoLibro *last){
  54.  
  55.      NodoLibro * n1,*n2;
  56.      NodoLibro *pivote=first;
  57.      int longitud = distancia(first,last);
  58.      int i,j;
  59.      if (longitud<=1)
  60.       return;
  61.  
  62.      
  63.      n1 = first;
  64.      n2 = last;
  65.     
  66.          i=1;
  67.      j=longitud;
  68.  
  69.     
  70.      while (i<j){   
  71.  
  72.      while (!n1->compare(pivote) && i<j+1 && i<longitud){
  73.          n1=n1->siguiente;
  74.          i++;
  75.      }
  76.  
  77.       while (n2->compare(pivote) && j>i-1 && j>1){
  78.         n2 = n2->anterior;
  79.         j--;
  80.      }
  81.  
  82.      if (i<j)
  83.       n1->changeLibro(n2);
  84.      }
  85.      
  86.  
  87.      pivote->changeLibro(n2);
  88.     
  89.      if (n2!=first)
  90.       QuicksortAux(first,n2->anterior);
  91.      if (n2!=last)
  92.      QuicksortAux(n2->siguiente,last);
  93.     
  94.     }
  95.  
  96. public:
  97.  
  98.    
  99.     Lista()
  100.     {
  101.         primero = ultimo = NULL;
  102.     }
  103.     ~Lista()
  104.     {
  105.         NodoLibro * temp = primero, * temp2;
  106.         while (temp != NULL) {
  107.             temp2 = temp->siguiente;
  108.             delete temp;
  109.             temp = temp2;
  110.         }
  111.     }
  112.     
  113.     void Append(libro * l)
  114.     {
  115.         NodoLibro * n = new NodoLibro(l);
  116.         if (ultimo  == NULL )
  117.             primero = ultimo = n;
  118.         else{
  119.             n->siguiente = NULL;
  120.             ultimo->siguiente = n;
  121.             n->anterior = ultimo;
  122.             ultimo = n;
  123.         }
  124.     } 
  125.     libro * Remove ()
  126.     {
  127.         NodoLibro * n = ultimo;
  128.         libro * l = ultimo->lib;
  129.         if (ultimo == primero)
  130.             ultimo = primero = NULL;
  131.         else{
  132.             ultimo = ultimo->anterior;
  133.             ultimo->siguiente = NULL;
  134.         }
  135.         delete n;
  136.         return l;
  137.         
  138.     }
  139.     
  140.     void printlista()
  141.     {
  142.         NodoLibro * temp = primero;
  143.         while (temp != NULL){
  144.             temp->lib->printlibro();
  145.             temp = temp->siguiente;
  146.         }
  147.     }
  148.  
  149.     
  150.  
  151.     
  152.     
  153.     void OrdenarLista()
  154.     {
  155.         NodoLibro * n1,*n2;
  156.         for (n1 = ultimo; n1 != primero ; n1 = n1->anterior)
  157.             for (n2 = primero; n2 != n1 ; n2 = n2->siguiente)
  158.             {
  159.                 if (n2->compare(n2->siguiente))
  160.                     n2->changeLibro(n2->siguiente);
  161.                     
  162.             }
  163.     }
  164.  
  165.     void Quicksort(){
  166.     if (primero!=ultimo)
  167.      QuicksortAux(primero,ultimo);
  168.     }
  169.  
  170.  
  171.     
  172. } ;


Puede mejorarse mucho, por ejemplo, utilizando otro tipo de ordenación cuando el tamaño de las sublistas sea menor de un número o utilizando una versión iterativa en vez de iterativa.
Última edición por alexg88; 13/05/2011 a las 16:10