Ordinamento di un elenco collegato in Java

Question

Ho scritto un algoritmo di ordinamento delle bolle per ordinare un elenco collegato. Sono un principiante di Java e sto provando ad apprendere strutture dati. Sono confuso perché il mio secondo elemento non è ordinato correttamente.

EDIT

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

Questa è l'uscita sto ottenendo

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

Oltre So che lo scenario peggiore di un bubble sort è O (n). Posso usare mergesort su una lista collegata per avere una complessità temporale migliore?

Grazie!

Answer 1

Esistono molti algoritmi di ordinamento che funzionano sugli elenchi collegati e in questo caso il Mergesort funziona in modo eccellente. Ho scritto an earlier answer to a question about sorting linked lists che esplora molti algoritmi di ordinamento classici sugli elenchi collegati, insieme alle loro complessità di tempo e spazio. È possibile utilizzare l'ordinamento di inserimento, l'ordinamento di selezione, il mergesort e il quicksort su elenchi collegati. Con un po 'di confusione, puoi anche far funzionare heapsort. La mia risposta precedente ha dettagli su come farlo.

Per quanto riguarda il codice, notare che nel vostro ciclo interno si avanza j avanti fino a quando il puntatore next diventa null. A questo punto, non è mai possibile reimpostare j in modo diverso, quindi in ogni iterazione futura del ciclo esterno il ciclo interno non viene mai eseguito. Probabilmente dovresti impostare j = i.next all'inizio di ogni iterazione. Inoltre, probabilmente non si desidera interrompere il ciclo quando j.next è nullo, ma piuttosto quando j è nullo, poiché altrimenti si salta l'ultimo elemento dell'array.

Inoltre, l'algoritmo di ordinamento che hai scritto qui è selection sort piuttosto che bubble sort, perché si sta facendo molti passi sopra la lista collegata alla ricerca del più piccolo elemento che non si è ancora posizionato. Non so se questo è un problema o no, ma non ero sicuro se ne fossi a conoscenza. Detto questo, penso che sia probabilmente una buona cosa, dato che il bubble sort è meno efficiente della selezione nella maggior parte dei casi (a meno che la lista sia già vicina all'ordinamento).

Spero che questo aiuti!