ordinamento di una lista doppiamente collegata con un tipo di unione

Ho trovato questo codice in internet ed era per gli array, voglio cambiarlo per la lista doppiamente collegata (invece dell’indice dovremmo usare il puntatore), per favore aiutatemi come posso cambiare il metodo di fusione (ho cambiato metodo di ordinamento da solo) anche questo non è il mio lavoro a casa, mi piace lavorare con la lista collegata !!

public class MergeSort { private DoublyLinkedList LocalDoublyLinkedList; public MergeSort(DoublyLinkedList list) { LocalDoublyLinkedList = list; } public void sort() { if (LocalDoublyLinkedList.size() <= 1) { return; } DoublyLinkedList listOne = new DoublyLinkedList(); DoublyLinkedList listTwo = new DoublyLinkedList(); for (int x = 0; x < (LocalDoublyLinkedList.size() / 2); x++) { listOne.add(x, LocalDoublyLinkedList.getValue(x)); } for (int x = (LocalDoublyLinkedList.size() / 2) + 1; x < LocalDoublyLinkedList.size`(); x++) {` listTwo.add(x, LocalDoublyLinkedList.getValue(x)); } //Split the DoublyLinkedList again MergeSort sort1 = new MergeSort(listOne); MergeSort sort2 = new MergeSort(listTwo); sort1.sort(); sort2.sort(); merge(listOne, listTwo); } private void merge(DoublyLinkedList a, DoublyLinkedList b) { int x = 0; int y = 0; int z = 0; while (x < first.length && y < second.length) { if (first[x] < second[y]) { a[z] = first[x]; x++; } else { a[z] = second[y]; y++; } z++; } //copy remaining elements to the tail of a[]; for (int i = x; i < first.length; i++) { a[z] = first[i]; z++; } for (int i = y; i < second.length; i++) { a[z] = second[i]; z++; } } } 

Unisci ordinamento richiede dividere l’elenco abbastanza spesso. Non sta iterando al centro di una LinkedList praticamente l’operazione più costosa che puoi eseguire su di essa (beh, a meno di ordinarla)? Ho visto che la fase di unione funziona abbastanza bene (stai procedendo con iterazioni su due elenchi collegati), ma non sono sicuro che questa implementazione valga la pena senza un’operazione di divisione O (1) .

Azione supplementare

Come ho sottolineato, l’operazione di divisione O (n) non aggiunge molto alla complessità quando stai già facendo O (n) cose durante la fase di fusione. Ciononostante, hai ancora problemi a fare l’iterazione come stai facendo (non usando un Iterator ma usando invece get su una List con caratteristiche di accesso casuale scadenti).

Mi sono annoiato mentre eseguivo il debug di un altro problema, quindi ti ho scritto quello che considero un’implementazione Java decente di questo algoritmo. Ho seguito verbatim pseudocode di Wikipedia e spruzzato in alcuni generici e dichiarazioni di stampa. Se avete domande o dubbi, basta chiedere.

 import java.util.List; import java.util.LinkedList; /** * This class implements the mergesort operation, trying to stay * as close as possible to the implementation described on the * Wikipedia page for the algorithm. It is meant to work well * even on lists with non-constant random-access performance (ie * LinkedList), but assumes that {@code size()} and {@code get(0)} * are both constant-time. * * @author jasonmp85 * @see Merge sort */ public class MergeSort { /** * Keeps track of the call depth for printing purposes */ private static int depth = 0; /** * Creates a list of 10 random Longs and sorts it * using {@link #sort(List)}. * * Prints out the original list and the result. * */ public static void main(String[] args) { LinkedList list = new LinkedList(); for(int i = 0; i < 10; i++) { list.add((long)(Math.random() * 100)); } System.out.println("ORIGINAL LIST\n" + "=================\n" + list + "\n"); List sorted = sort(list); System.out.println("\nFINAL LIST\n" + "=================\n" + sorted + "\n"); } /** * Performs a merge sort of the items in {@code list} and returns a * new List. * * Does not make any calls to {@code List.get()} or {@code List.set()}. * * Prints out the steps, indented based on call depth. * * @param list the list to sort */ public static > List sort(List list) { depth++; String tabs = getTabs(); System.out.println(tabs + "Sorting: " + list); if(list.size() <= 1) { depth--; return list; } List left = new LinkedList(); List right = new LinkedList(); List result = new LinkedList(); int middle = list.size() / 2; int added = 0; for(T item: list) { if(added++ < middle) left.add(item); else right.add(item); } left = sort(left); right = sort(right); result = merge(left, right); System.out.println(tabs + "Sorted to: " + result); depth--; return result; } /** * Performs the oh-so-important merge step. Merges {@code left} * and {@code right} into a new list, which is returned. * * @param left the left list * @param right the right list * @return a sorted version of the two lists' items */ private static > List merge(List left, List right) { String tabs = getTabs(); System.out.println(tabs + "Merging: " + left + " & " + right); List result = new LinkedList(); while(left.size() > 0 && right.size() > 0) { if(left.get(0).compareTo(right.get(0)) < 0) result.add(left.remove(0)); else result.add(right.remove(0)); } if(left.size() > 0) result.addAll(left); else result.addAll(right); return result; } /** * Returns a number of tabs based on the current call depth. * */ private static String getTabs() { StringBuffer sb = new StringBuffer(""); for(int i = 0; i < depth; i++) sb.append('\t'); return sb.toString(); } } 

Correre

  1. Salvare il codice in un file denominato MergeSort.java
  2. Esegui javac MergeSort.java
  3. Esegui java MergeSort
  4. meraviglia
  5. Facoltativamente, esegui javadoc -private MergeSort.java per creare la documentazione. Apri il file index.html che crea.

Dipende da cosa è DoublyLinkedList – è un tipo concreto definito dall’utente, o solo un nome alias per un tipo di elenco collegato?

Nel primo caso, dovresti avere metodi di get / set indicizzati e / o un iteratore definito in esso, che rendono l’attività semplice.

In quest’ultimo caso, perché non utilizzare lo standard java.util.LinkedList ?

In termini di interfaccia List , l’operazione potrebbe essere implementata in questo modo:

  List merge(List first, List second, List merged) { if (first.isEmpty()) merged.adAll(second); else if (second.isEmpty()) merged.adAll(first); else { Iterator firstIter = first.iterator(); Iterator secondIter = second.iterator(); T firstElem = firstIter.next(); T secondElem = secondIter.next(); do { if (firstElem < secondElem) { merged.add(firstElem); firstElem = firstIter.hasNext() ? firstIter.next() : null; } else { merged.add(secondElem); secondElem = secondIter.hasNext() ? secondIter.next() : null; } } while (firstIter.hasNext() && secondIter.hasNext()); //copy remaining elements to the tail of merged if (firstElem != null) merged.add(firstElem); if (secondElem != null) merged.add(secondElem); while (firstIter.hasNext()) { merged.add(firstIter.next()); } while (secondIter.hasNext()) { merged.add(secondIter.next()); } } } 

Questa implementazione è un po 'più noiosa di quella con gli array, soprattutto perché gli iteratori sono "consumati" dall'operazione next , quindi è necessario tenere conto dell'elemento corrente in ogni elenco. Con get , il codice sarebbe più semplice, abbastanza simile alla soluzione array, tuttavia sarebbe molto più lento per le grandi liste, come ha sottolineato @ sepp2k.

Ancora un paio di note:

  • la tradizione Java consiste nell'utilizzare nomi di variabili in localDoublyLinkedList minuscole, quindi localDoublyLinkedList
  • Java non ha puntatori, solo riferimenti.

Mi sono imbattuto in questo problema ieri. Ecco alcuni pensieri.

L’ordinamento di DoublyLinkedList è diverso DoublyLinkedList di una Array poiché non è ansible creare riferimenti basati su indici a nessun elemento arbitrario nell’elenco. Invece è necessario ricordare gli elementi durante ogni passaggio ricorsivo e quindi passarli alla funzione di unione. Per ogni passo di ricorsione devi solo ricordare il primo elemento di ciascuna lista. Se non ricordi questi elementi, ti ritroverai rapidamente con gli indici, ma questo ti porta al problema che nella tua funzione di merge devi attraversare l’intera lista con -loops per trovare gli elementi da unire. Questo a sua volta significa che ottieni una complessità di O(n^2) .

Un altro punto importante è la fase di ricorrere nella lista e dividere la lista in due metà. È ansible eseguire questo passaggio nella parte ricorsiva utilizzando for -loops. Contrariamente alla parte merge in questo passaggio, for -loops produrrà solo una complessità di O(log(n) * n/2) e questo è ancora al di sotto della complessità complessiva di O(n*log(n)) . Ecco perché:

  1. Devi sempre trovare il primo elemento di ciascuna metà della lista.

  2. Nel primo passaggio di ricorsione devi passare il first object e l’object nella posizione n/2 . Questo richiede n/2 passi per trovare.

  3. In ogni passo successivo devi trovare l’object intermedio per ciascuna delle due metà dell’elenco che ci dà n/4 per trovare l’object nella prima metà e n/4 nell’altra metà. In totale è n/2 .

  4. In ciascuna fase ricorsiva successiva la quantità di parti della lista doppie e le lunghezze è divisa per due:

    • 4 * n/8 nella terza profondità di ricorsione

    • 8 * n/16 nella quarta profondità di ricorsione, e così via …

  5. La profondità di ricorsione è log(n) e in ogni fase eseguiamo n/2 passi. Questo è uguale a O(log(n)*n/2)

Finalmente ecco un codice:

 public DoublyLinkedList mergesort(DoublyLinkedList in, int numOfElements) { in.first = mergesort(in.first, numOfElements); return in; } 

Mergesort:

 public ListElement mergesort(ListElement first, int length) { if(length > 1) { ListElement second = first; for(int i=0; i 

e unire:

 public ListElement merge(ListElement first, ListElement second, int length) { ListElement result = first.prev; //remember the beginning of the new list will begin after its merged int right = 0; for(int i=0; i 

Anche la quantità massima di memoria utilizzata è piuttosto bassa (escludendo la lista stessa). Correggimi se ho torto ma dovrebbe essere inferiore a 400 byte (su 32 bit). Sarebbe 12 byte per chiamata su mergeSort moltiplicato per la profondità di ricorsione del log (n) più 20 byte per le variabili di unione: 12 * log (n) +20 byte.

Codice PS testato su 1 milione di articoli (richiede 1200ms). Anche DoublyLinkedList è un contenitore che memorizza il primo ListElement dell'elenco.

Aggiornamento: ho risposto a una domanda simile su Quicksort usando le stesse strutture di dati, tuttavia rispetto a questa implementazione di Mergesort funziona molto più lentamente. Ecco alcuni timing aggiornati per riferimento:

mergesort:

 1.000.000 Items: 466ms 8.300.000 Items: 5144ms 

quicksort:

 1.000.000 Items: 696ms 8.300.000 Items: 8131ms 

Nota che i tempi sono specifici per il mio hardware e potresti ottenere risultati diversi.

Prima di tutto, NON è necessario utilizzare gli indici quando si tratta di elenchi collegati. Fai cosi:

 while (i < in.size/2){ listOne.addLast( in.remove(in.first()) ); i++ } while(!in.isEmptly){ listTwo.addLast( in.remove(in.first()) ); } 

E per la fusione

 merge(a, b, out){ while(!a.empty && !b.empty){ if(a.first() >= b.first()) out.addLast( a.remove(a.first()) ); else out.addLast( b.remove(b.first()) ); //remember to take care of the remaining elements while(!a.empty) out.addLast( a.remove(a.first()) ); while(!b.empty) out.addLast( b.remove(b.first()) ); } 

In questo modo sarà ancora O (n log n)

Un’altra idea è quella di creare un array con tutti gli elementi dell’elenco, ordinare l’array e quindi inserire di nuovo gli elementi nell’elenco.

Pro: molto semplice da implementare, più veloce se scarsa implementazione di list mergesort (forse anche più veloce di buone implementazioni)

Contro: usa dello spazio extra (O (n))