Ordenar una lista vinculada en Java

Question

He escrito un algoritmo de ordenación de burbujas para ordenar una lista vinculada. Soy un principiante de Java e intento aprender estructuras de datos. Estoy confundido por qué mi segundo elemento no está ordenado correctamente.

EDITAR

class SListNode { 
    Object item; 
    SListNode next; 


    SListNode(Object obj) { 
    item = obj; 
    next = null; 
    } 


    SListNode(Object obj, SListNode next) { 
    item = obj; 
    this.next = next; 
    } 

} 
public class SList { 

    private SListNode head; 
    private SListNode temp; 

    public void sortList() { 
     SListNode node = head,i,j; 
     head = node; 
     i = node; 
     j = node.next; 
     while(i.next != null) { 
      while(j.next != null) { 
       if((Integer)i.item < (Integer)j.item) { 
        temp = i.next; 
        i.next = j.next; 
        j.next = temp; 
       } 
       j = j.next; 
      } 
      i = i.next; 
     } 
    } 
} 

Ésta es la salida que estoy recibiendo

List after construction: [ 3 6 9 4 12 15 ] 
After sorting: [ 3 4 9 12 6 15 ] 

Además sé que el peor de los casos de una especie de burbuja es O (n 2 ). ¿Puedo usar mergesort en una lista vinculada para tener una mejor complejidad de tiempo?

Gracias!

Answer 1

Hay muchos algoritmos de clasificación que funcionan en listas vinculadas y mergesort funciona excelentemente en este caso. Escribí an earlier answer to a question about sorting linked lists que explora muchos algoritmos de clasificación clásicos en listas vinculadas, junto con sus complejidades de tiempo y espacio. Puede usar la ordenación por inserción, la ordenación por selección, el mergeort y el quicksort en las listas vinculadas. Con un poco de fudge, también puede obtener heapsort funcionando. Mi respuesta anterior tiene detalles sobre cómo hacer esto.

Con respecto a su código, observe que en su bucle interno se avanza j hacia adelante hasta que el puntero se convierte en nextnull. En este punto, nunca reinicia j para que sea otra cosa, por lo que en cada iteración futura del bucle externo, el bucle interno nunca se ejecuta. Probablemente deberías establecer j = i.next al comienzo de cada iteración. Además, probablemente no desee que el ciclo se detenga cuando j.next sea nulo, sino cuando j sea nulo, ya que de lo contrario omite el último elemento de la matriz.

Además, el algoritmo de ordenación que ha escrito aquí es selection sort en lugar de ordenamiento de burbuja, porque usted está haciendo muchos pases sobre la lista enlazada buscando el elemento más pequeño que usted no ha colocado todavía. No sé si esto es un problema o no, pero no estaba seguro de si era consciente de esto. Dicho esto, creo que eso es probablemente una buena cosa, ya que el ordenamiento de burbujas es menos eficiente que el ordenamiento por selección en la mayoría de los casos (a menos que la lista ya esté próxima a ser ordenada).

Espero que esto ayude!