Ordenar una lista enlazada

Clasificación de listas enlazadas . La gran mayoría de los algoritmos de clasificación requieren para su trabajo la capacidad de acceder a los elementos de la lista ordenada por sus números de serie (índices). En las listas enlazadas , donde los elementos se almacenan sin ordenar, acceder a un elemento por su número es una operación que consume muchos recursos y requiere comparaciones y accesos a la memoria en promedio. Como resultado, el uso de algoritmos de clasificación típicos se vuelve extremadamente ineficiente. Sin embargo, las listas enlazadas tienen la ventaja de poder fusionar dos listas ordenadas en una a la vez sin usar memoria adicional.

Concatenación de dos listas ordenadas

Digamos que tenemos una lista enlazada individualmente cuyos elementos están descritos por una estructura ( ejemplo de Pascal ):

escriba PList_Item = ^ TList_Item ; TList_Item = registro Clave : Entero ; Siguiente : PList_Item ; fin ; var Lista : PList_Item ; // Puntero a la lista

El algoritmo es bastante simple: en la entrada hay punteros a los primeros elementos de las listas combinadas. El elemento con la clave más pequeña se selecciona como el comienzo de la lista resultante. Luego, como los siguientes elementos de la lista resultante, se seleccionan los elementos subsiguientes de la primera o segunda lista fuente, con un valor clave más pequeño. Cuando se alcanza el último elemento de una de las listas de entrada, el puntero del último elemento de la lista resultante se establece en el resto de la otra lista de entrada.

function IntersectSorted ( const pList1 , pList2 : PList_Item ) : PList_Item ; var pCurItem : PList_Item ; p1 , p2 : PList_Item ; comenzar p1 := pLista1 ; p2 := pLista2 ; si p1 ^. Clave <= p2 ^. Tecla luego comenzar pCurItem := p1 ; p1 := p1 ^. siguiente ; end else begin pCurItem := p2 ; p2 := p2 ^. siguiente ; fin ; Resultado := pCurItem ; mientras que ( p1 < > nil ) y ( p2 <> nil ) comienzan si p1 ^. Clave <= p2 ^. Tecla luego comenzar pCurItem ^. Siguiente := p1 ; pCurItem := p1 ; p1 := p1 ^. siguiente ; fin si no comienza pCurItem ^. Siguiente := p2 ; pCurItem := p2 ; p2 := p2 ^. siguiente ; fin ; fin ; si p1 <> nil entonces pCurItem ^. Siguiente := p1 más pCurItem ^. Siguiente := p2 ; fin ;

Ordenar una lista enlazada individualmente

El proceso de ordenar una lista es un paso secuencial a través de la lista, ordenando primero los pares de elementos, luego cada par de pares de elementos, combinándolos en listas de 4 elementos, luego se combinan las listas resultantes de 8, 16, etc. elementos.

La implementación propuesta utiliza una pila de listas. El tamaño de pila requerido es [log 2 n ] + 1, donde n es el número de elementos en la lista. Si el número de elementos no se conoce de antemano, entonces se puede establecer una profundidad de pila suficiente por adelantado. Entonces, por ejemplo, una pila de 32 elementos de profundidad se puede usar para ordenar listas de hasta 4,294,967,295 elementos. La pila almacena punteros a las partes ordenadas de la lista, y el nivel es en realidad log 2 i + 1, donde i es el número de elementos en esa parte de la lista.

La esencia del algoritmo es la siguiente: la lista se recorre secuencialmente, y cada elemento se convierte en una lista degenerada al eliminar el puntero al siguiente elemento. Un puntero a la lista creada de esta manera se coloca en la pila, con el nivel establecido en 1, después de lo cual se realiza una verificación: si los dos últimos elementos de la pila tienen el mismo valor de nivel, se extraen de la pila. , las listas a las que apuntan estos elementos se fusionan y la lista resultante se coloca en la pila en un nivel superior al anterior. Esta unión se repite hasta que los niveles de los dos últimos elementos sean iguales, o hasta llegar al tope de la pila. Una vez recorrida por completo la lista inicial, las listas enumeradas en la pila se combinan, independientemente de su nivel. La lista resultante de la unión es la deseada, con los elementos ordenados

escriba TSortStackItem = nivel de registro : entero ; Artículo : PList_Item ; fin ; var Stack : Array [ 0 .. 31 ] de TSortStackItem ; StackPos : Entero ; p : PList_Elemento ; comenzar StackPos := 0 ; p := Lista ; mientras que p < > nil comienza Stack [ StackPos ] . Nivel := 1 ; Pila [ StackPos ] . Artículo := p ; pag := pag ^. siguiente ; Pila [ StackPos ] . Artículo ^. Siguiente := nil ; Inc ( StackPos ) ; while ( StackPos > 1 ) y ( Stack [ StackPos - 1 ] . Level = Stack [ StackPos - 2 ] . Level ) comienzan Stack [ StackPos - 2 ] . _ Elemento := IntersectSorted ( Pila [ StackPos - 2 ] . Elemento , Pila [ StackPos - 1 ] . Elemento ) ; Inc ( Pila [ StackPos - 2 ] . Nivel ) ; diciembre ( posición de pila ) ; fin ; fin ; mientras que StackPos > 1 comienza Stack [ StackPos - 2 ] . Elemento := IntersectSorted ( Pila [ StackPos - 2 ] . Elemento , Pila [ StackPos - 1 ] . Elemento ) ; Inc ( Pila [ StackPos - 2 ] . Nivel ) ; diciembre ( posición de pila ) ; fin ; si StackPos > 0 entonces List := Stack [ 0 ] . artículo ; fin ;

Complejidad del algoritmo

Obviamente, la complejidad del algoritmo es O( n log n ), mientras que los requisitos de memoria son mínimos O(log n )

Ordenar una lista doblemente enlazada

Dado que el número de operaciones excede el número de elementos en la lista, la solución más óptima cuando se ordena una lista doblemente enlazada es ordenar la lista como una lista con un solo enlace, usando solo punteros a los elementos subsiguientes, y después de ordenar, restaurar los punteros a los elementos anteriores. elementos. La complejidad de tal operación es siempre O(n).

escriba PList_Item = ^ TList_Item ; TList_Item = registro Clave : Entero ; Anterior , Siguiente : PList_Item ; fin ; var // Punteros al primer y último elemento de la lista First , Last : PList_Item ; p := Primero ; // Comprobar si la lista no está vacía if p <> nil luego comenzar p ^. Anterior := nil ; mientras p ^. Siguiente <> nil do begin p ^. Siguiente ^. anterior := p ; pag := pag ^. siguiente ; fin ; fin ; Último := pag ;

Véase también

Literatura