java - sort - ordenar una lista doblemente vinculada con tipo de fusión

merge two singly linked list in c++

Question

Encontré este código en internet y fue para matrices, quiero cambiarlo por una lista doblemente enlazada (en lugar de índice debemos usar un puntero) ¿Podrían ayudarme por favor? ¿Cómo puedo cambiar el método de fusión? (He cambiado el método de clasificación) por mi cuenta) también este no es mi trabajo a domicilio, ¡¡¡me encanta trabajar con la lista vinculada !!

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

Answer 1

Depende de qué es DoublyLinkedList : ¿es un tipo concreto definido por el usuario o solo un nombre de alias para un tipo de lista vinculada?

En el primer caso, debe tener indexados los métodos get / set y / o un iterador definido en él, lo que simplifica la tarea.

En este último caso, ¿por qué no utilizar el estándar java.util.LinkedList ?

En términos de la interfaz de la List , la operación podría implementarse así:

<T> List<T> merge(List<T> first, List<T> second, List<T> merged) {
if (first.isEmpty())
merged.adAll(second);
else if (second.isEmpty())
merged.adAll(first);
else {
Iterator<T> firstIter = first.iterator();
Iterator<T> 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());
}
}
}

Esta implementación es un poco más tediosa de lo que sería con las matrices, sobre todo porque los iteradores son "consumidos" por la next operación, por lo que uno debe mantener la cuenta del elemento actual en cada lista. Con get , el código sería más simple, bastante similar a la solución de matriz, sin embargo sería mucho más lento para grandes listas, como señaló @ sepp2k.

Un par de notas más:

• la tradición de Java es usar nombres de variables en minúsculas, por localDoublyLinkedList tanto localDoublyLinkedList
• Java no tiene punteros, solo referencias.

Answer 2

En primer lugar, NO debes usar índices al tratar con listas enlazadas. Hazlo asi:

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

Y para fusionarse

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

De esta manera, seguirá siendo O (n log n)

Answer 3

La clasificación por fusión requiere dividir la lista con bastante frecuencia. ¿No es iterar en el medio de una LinkedList casi la operación más cara que puede realizar en ella (bueno, sin clasificarla)? Pude ver que el paso de fusión funciona bastante bien (estás iterando hacia adelante en dos listas enlazadas), pero no estoy seguro de que esta implementación valga la pena sin una operación dividida O (1) .

Seguir

Como se me indicó, la operación dividida O (n) realmente no agrega mucho a la complejidad cuando ya estás haciendo O (n) cosas durante la fase de fusión. Sin embargo, todavía te vas a encontrar con problemas para hacer iteraciones como lo estás haciendo (no usando un Iterator sino usando una List con pobres características de acceso aleatorio).

Estaba aburrido mientras depuraba algún otro problema, así que escribí lo que considero una implementación Java decente de este algoritmo. Seguí literalmente el pseudocódigo de Wikipedia y salpicado en algunos genéricos e impresos. Si tiene alguna pregunta o inquietud, solo pregunte.

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 (i.e.
* LinkedList), but assumes that {@code size()} and {@code get(0)}
* are both constant-time.
*
* @author jasonmp85
* @see <a href="http://en.wikipedia.org/wiki/Merge_sort">Merge sort</a>
*/
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<Long> list = new LinkedList<Long>();
for(int i = 0; i < 10; i++) {
list.add((long)(Math.random() * 100));
}
System.out.println("ORIGINAL LIST/n" +
"=================/n" +
list + "/n");
List<Long> 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 <T extends Comparable<T>> List<T> sort(List<T> list) {
depth++;
String tabs = getTabs();
System.out.println(tabs + "Sorting: " + list);
if(list.size() <= 1) {
depth--;
return list;
}
List<T> left = new LinkedList<T>();
List<T> right = new LinkedList<T>();
List<T> result = new LinkedList<T>();
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 <T extends Comparable<T>> List<T> merge(List<T> left,
List<T> right) {
String tabs = getTabs();
System.out.println(tabs + "Merging: " + left + " & " + right);
List<T> result = new LinkedList<T>();
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();
}
}

Correr

1. Guarde el código en un archivo llamado MergeSort.java
2. Ejecute javac MergeSort.java
3. Ejecute java MergeSort
4. Maravilla
5. Opcionalmente, ejecute javadoc -private MergeSort.java para crear la documentación. Abra el archivo index.html que crea.

Answer 4

Otra idea es crear una matriz con todos los elementos de la lista, ordenar la matriz e insertar nuevamente los elementos en la lista.

Pro: muy simple de implementar, más rápido si la implementación es deficiente de la lista mergesort (quizás también más rápido que las buenas implementaciones)

Contra: utiliza un poco de espacio extra (O (n))

Answer 5

Me encontré con este problema ayer. Aquí hay algunos pensamientos.

La clasificación de una lista DoublyLinkedList es diferente de ordenar una Array ya que no puede hacer referencias basadas en el índice a ningún elemento arbitrario en la lista. En su lugar, debe recordar los elementos durante cada paso recursivo y luego pasarlos a la función de fusión. Para cada paso de recursividad, solo necesita recordar el primer elemento de cada mitad de la lista. Si no recuerda estos elementos, terminará rápidamente con índices, pero esto le lleva al problema de que en su merge -función que necesita recorrer toda la lista for -ops para encontrar los elementos para fusionar. Eso a su vez significa que obtienes una complejidad de O(n^2) .

Otro punto importante es el paso de recurrir a la lista y dividir la lista en dos mitades. Puedes hacer este paso en la parte recursiva usando for -loops. Contrariamente a la parte merge en este paso, for -loops solo arrojará una complejidad de O(log(n) * n/2) y esto aún está por debajo de la complejidad O(n*log(n)) . Aquí es por qué:

1. Siempre necesita encontrar el primer elemento de cada mitad de la parte de la lista.

2. En el primer paso de recursión, debe pasar el first elemento y el elemento en la posición n/2 . Esto toma n/2 pasos para encontrar.

3. En cada paso siguiente necesita encontrar el elemento del medio para cada una de las dos mitades de la lista, lo que nos da n/4 para encontrar el elemento en la primera mitad y n/4 en la otra mitad. En total eso es n/2 .

4. En cada paso recursivo siguiente, la cantidad de partes de la lista se duplica y las longitudes se dividen en dos:

   • 4 * n/8 en la tercera profundidad de recursión

   • 8 * n/16 en la 4ta profundidad de recursión, y así sucesivamente ...

5. La profundidad de recursión es log(n) y en cada paso llevamos a cabo n/2 pasos. Esto es igual a O(log(n)*n/2)

Finalmente, aquí hay un código:

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<length/2; i++) {
second = second.next;
}
first = mergesort(first, length/2);
second = mergesort(second, (length+1)/2);
return merge(first, second, length);
} else {
return first;
}
}

y fusionar:

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<length; i++) {
if(first.getKey() <= second.getKey()) {
if(first.next == second) break; //end of first list and all items in the second list are already sorted, thus break
first = first.next;
} else {
if(right==(length+1)/2)
break; //we have merged all elements of the right list into the first list, thus break
if(second == result) result = result.prev; //special case that we are mergin the last element then the result element moves one step back.
ListElement nextSecond = second.next;
//remove second
second.prev.next = second.next;
second.next.prev = second.prev;
//insert second behind first.prev
second.prev = first.prev;
first.prev.next = second;
//insert second before first
second.next = first;
first.prev = second;
//move on to the next item in the second list
second = nextSecond;
right++;
}
}
return result.next; //return the beginning of the merged list
}

La cantidad máxima de memoria utilizada también es bastante baja (sin incluir la lista). Corrígeme si me equivoco, pero debería tener menos de 400 bytes (en 32 bits). Sería 12 bytes por llamada en mergeSort veces la profundidad de recursión de log (n) más 20 bytes para las variables de fusión por lo tanto: 12 * log (n) +20 bytes.

Código PS probado en 1 millón de elementos (toma 1200ms). También DoublyLinkedList es un contenedor que almacena el primer ListElement de la lista.

Actualización: He respondido una pregunta similar sobre Quicksort usando las mismas estructuras de datos, sin embargo, en comparación con esta implementación de Mergesort, se ejecuta mucho más lento. Aquí hay algunos tiempos actualizados para referencia:

Mergesort:

1.000.000 Items: 466ms
8.300.000 Items: 5144ms

Ordenación rápida:

1.000.000 Items: 696ms
8.300.000 Items: 8131ms

Tenga en cuenta que los tiempos son específicos de mi hardware y es posible que obtenga diferentes resultados.