Ordene una sola lista vinculada

Question

¿Cómo clasificaría una sola lista vinculada? (el problema aquí es la propiedad individual + utilizando LinkedList para la clasificación es más difícil que una matriz) tuve gustaría ver un pseudo código ..

tratar de hacerlo lo más eficiente posible de tiempo y espacio.

Gracias!

Answer 1

Mergesorting involucra a pocos pasos simples:

1. Comprobar si la lista se vacío o tiene un solo elemento. Si es así, devuelva la lista sin cambios.

2. Divida la lista por la mitad. Mergesort ambas partes.

3. Combine las listas sacando repetidamente el elemento más pequeño de ambas listas.Dado que las listas de piezas ya están clasificadas, solo se trata de mirar los primeros elementos en ambas listas y elegir el más pequeño.

4. Regresar la lista fusionada.

Como resultado, obtendrá una lista vinculada ordenada en orden de menor elemento primero.

Ejemplo de código en Haskell:

import Data.List(splitAt) 

--Mergesorts a list by smallest element first. 
sort :: Ord a => [a] -> [a] 
sort = sortBy (<) 

--Generic sort that can sort in any order. 
sortBy :: (a -> a -> Bool) -> [a] -> [a] 
sortBy _ [] = [] 
sortBy _ [x] = [x] 
sortBy f xs = merge f (sortBy f first) (sortBy f second) 
    where 
     (first,second) = split xs 

--Splits a list in half. 
split :: [a] -> ([a],[a]) 
split xs = splitAt (halfLength xs) xs 

--Returns a lists length divided by two as a whole number (rounded). 
halfLength :: [a] -> Int 
halfLength = round . (/2) . fromIntegral . length 

--Merges two lists in the provided order. 
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a] 
merge _ [] [] = [] 
merge _ [] (y:ys) = y:ys 
merge _ (x:xs) [] = x:xs 
merge f (x:xs) (y:ys) = 
    if f x y 
     then x : merge f xs (y:ys) 
     else y : merge f (x:xs) ys 

Answer 2

El tipo de inserción y el QuickSort se pueden realizar en una lista de enlace único con la misma eficacia que en un conjunto.

Answer 3

Dado que una lista vinculada es simplemente una serie de elementos señalados por otros elementos, puede construir una matriz de punteros con O (n) tiempo y O (n) espacio, ordenarlos utilizando cualquiera de los excelentes algoritmos de clasificación con O (n log n) tiempo y O (1) espacio, luego reconstruye la lista vinculada desde cero con O (n) tiempo y O (1) espacio.

En general, ese es el tiempo O (n log n) y el espacio O (n).

Answer 4

Creo que puede hacer esto con una ordenación rápida in situ.
Estaba equivocado. Esto no funciona con una lista vinculada individualmente, ya que requiere poder dar un paso atrás en la lista.

Así que la verdadera pregunta es cómo hacer una clasificación rápida en el lugar.

Aquí vamos ...

1) Tome un puntero la primera, segunda y el último término de la lista enlazada,.
2) Paso del segundo puntero a través de la lista hasta que llegue a un término que es más grande que el primer término.
3) Pasa el tercer puntero hacia atrás en la lista hasta que toques un término que sea más pequeño que el primer término. Este paso no funciona con una lista vinculada individualmente.
4) Cambie los valores del segundo y tercer punteros.
5) Repita los pasos 2) a 5) hasta que el segundo y el tercer puntero se igualen.
6) Insertar el primer término después de la segunda puntero

-En este punto, la lista enlazada se divide en:
[términos menor que x] x [términos mayor que x]

7 Repita los pasos 2) a 7) para los [términos menores que x] y los [términos mayores que x] hasta que el tamaño del bloque [términos ________ que x] sea uno.

Espacio: 3 punteros por capa.
O (log (n))

Tiempo: Igual que el rápido Ordenado
O (n log (n)) en general
O (n * n) en el peor de los casos (si la lista es o bien ya ordenados o en orden inverso)

---

Editado para el formato y la estupidez

Answer 5

he estado pensando en esto un poco más, y creo que se logre el o (n log (n) el tiempo) y O (1) condición espacial con Merge ordenar.

Veamos ...
Tome la lista:
3 -> 2 -> 1 -> 5 -> 6 -> 4

Primer paso:
Establecer un puntero para el primero, segundo término y 3er términos
Establezca el término más pequeño entre el 1er y el segundo puntero para señalar el término más grande.
Establezca el último de los 2 términos para que apunte al resto de la lista original.
Repita hasta el final de la lista.
2 -> 3 -> 1 -> 5 -> 4 -> 6

En este punto, cada par de términos está ordenado.

pase enésimo:
Establecer un puntero a la primera, (2^(N-1)) -ésimo, y (2^(n)) + 1 th términos
Tome el nodo valorado más pequeño e incrementar su puntero .
Repita el proceso hasta que se agoten ambas listas (de longitud 2^N), añadiendo el nodo valorado más pequeño cada vez al nodo valorado más pequeño anterior.
Establezca el puntero al resto de la lista original.
Repita hasta el final de la lista.

pase 0 ª: 3 -> 2 -> 1 -> 5 -> 6 -> 4 (cada bloque de 1 plazo se ordena) (trivial)
primero pase: 2 -> 3 -> 1 -> 5 -> 4 -> 6 (se ordena cada bloque de 2 términos)
2º paso: 1 -> 2 -> 3 -> 5 -> 4 -> 6 (se ordena cada bloque de 4 términos)
3er paso: 1 -> 2 -> 3 -> 4 -> 5 -> 6 (se ordena cada bloque de 8 términos)

Tiempo: log (n) pasa, con n comparaciones para cada pase.
O (n log (n))

espacio: las variables de puntero y enteros
O (1)