¿Cuál es el algoritmo más rápido para ordenar una lista vinculada?

Tengo curiosidad por saber si O (n log n) es lo mejor que puede hacer una lista enlazada.

Es razonable esperar que no pueda hacerlo mejor que O (N log N) en tiempo de ejecución .

Sin embargo, la parte interesante es investigar si puede ordenarlo en el lugar , de manera estable , su peor comportamiento, etc.

Simon Tatham, de la fama de Putty, explica cómo ordenar una lista enlazada con ordenación por combinación . Concluye con los siguientes comentarios:

Como cualquier algoritmo de clasificación que se precie, tiene un tiempo de ejecución O (N log N). Debido a que se trata de Mergesort, el peor tiempo de ejecución sigue siendo O (N log N); no hay casos patológicos.

El requisito de almacenamiento auxiliar es pequeño y constante (es decir, algunas variables dentro de la rutina de clasificación). Gracias al comportamiento inherentemente diferente de las listas enlazadas de las matrices, esta implementación de Mergesort evita el costo de almacenamiento auxiliar O (N) normalmente asociado con el algoritmo.

También hay una implementación de ejemplo en C que funciona tanto para listas enlazadas simples como dobles.

Como @ Jørgen Fogh menciona a continuación, la notación Big-O puede ocultar algunos factores constantes que pueden hacer que un algoritmo funcione mejor debido a la ubicación de la memoria, debido a un número bajo de elementos, etc.

Dependiendo de varios factores, en realidad puede ser más rápido copiar la lista en una matriz y luego usar un Quicksort .

La razón por la que esto podría ser más rápido es que una matriz tiene un rendimiento de caché mucho mejor que una lista vinculada. Si los nodos de la lista están dispersos en la memoria, es posible que esté generando pérdidas de caché por todas partes. Por otra parte, si la matriz es grande, obtendrá pérdidas de caché de todos modos.

Mergesort tiene un mejor paralelismo, por lo que puede ser una mejor opción si eso es lo que desea. También es mucho más rápido si lo realiza directamente en la lista vinculada.

Dado que ambos algoritmos se ejecutan en O (n * log n), tomar una decisión informada implicaría perfilarlos a ambos en la máquina en la que le gustaría ejecutarlos.

--- EDITAR

Decidí probar mi hipótesis y escribí un programa en C que medía el tiempo (uso clock()) necesario para ordenar una lista enlazada de entradas. Intenté con una lista vinculada donde se asignó cada nodo conmalloc() y una lista vinculada donde los nodos se distribuyeron linealmente en una matriz, por lo que el rendimiento de la caché sería mejor. Los comparé con el qsort incorporado, que incluía copiar todo, desde una lista fragmentada a una matriz, y volver a copiar el resultado. Cada algoritmo se ejecutó en los mismos 10 conjuntos de datos y se promediaron los resultados.

Estos son los resultados:

N = 1000:

Lista fragmentada con clasificación de combinación: 0,000000 segundos

Matriz con qsort: 0.000000 segundos

Lista empaquetada con clasificación de combinación: 0,000000 segundos

N = 100000:

Lista fragmentada con clasificación de combinación: 0.039000 segundos

Matriz con qsort: 0.025000 segundos

Lista empaquetada con clasificación de combinación: 0,009000 segundos

N = 1000000:

Lista fragmentada con clasificación de combinación: 1,162000 segundos

Matriz con qsort: 0.420000 segundos

Lista empaquetada con clasificación de combinación: 0.112000 segundos

N = 100000000:

Lista fragmentada con clasificación de combinación: 364,797000 segundos

Matriz con qsort: 61.166000 segundos

Lista empaquetada con clasificación de combinación: 16.525000 segundos

Conclusión:

Al menos en mi máquina, vale la pena copiar en una matriz para mejorar el rendimiento de la caché, ya que rara vez tiene una lista vinculada completamente empaquetada en la vida real. Cabe señalar que mi máquina tiene un Phenom II de 2.8GHz, pero solo 0.6GHz de RAM, por lo que el caché es muy importante.

Los tipos de comparación (es decir, los basados ​​en elementos de comparación) no pueden ser más rápidos que n log n. No importa cuál sea la estructura de datos subyacente. Ver Wikipedia .

Otros tipos de tipos que aprovechan que hay muchos elementos idénticos en la lista (como el tipo de conteo), o alguna distribución esperada de elementos en la lista, son más rápidos, aunque no puedo pensar en ninguno que funcione particularmente bien en una lista vinculada.

Este es un bonito artículo sobre este tema. Su conclusión empírica es que Treesort es el mejor, seguido de Quicksort y Mergesort. La clasificación de sedimentos, la clasificación de burbujas y la clasificación de selección funcionan muy mal.

UN ESTUDIO COMPARATIVO DE ALGORITMOS DE CLASIFICACIÓN DE LISTAS VINCULADAS por Ching-Kuang Shene

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981

Como se ha dicho muchas veces, el límite inferior de la clasificación basada en la comparación para datos generales será O (n log n). Para resumir brevemente estos argumentos, hay n! diferentes formas de ordenar una lista. Cualquier tipo de árbol de comparación que tenga n! (que está en O (n ^ n)) las posibles clasificaciones finales necesitarán al menos log (n!) como altura: esto le da un límite inferior O (log (n ^ n)), que es O (n log n).

Entonces, para datos generales en una lista vinculada, la mejor clasificación posible que funcionará con cualquier dato que pueda comparar dos objetos será O (n log n). Sin embargo, si tiene un dominio más limitado de cosas en las que trabajar, puede mejorar el tiempo que lleva (al menos proporcional an). Por ejemplo, si está trabajando con números enteros que no superen algún valor, puede usar Ordenamiento por recuento o Ordenamiento por radix , ya que estos usan los objetos específicos que está ordenando para reducir la complejidad con proporción an. Sin embargo, tenga cuidado, estos agregan otras cosas a la complejidad que puede que no considere (por ejemplo, el ordenamiento por conteo y el ordenamiento por radix agregan factores que se basan en el tamaño de los números que está ordenando, O (n + k ) donde k es el tamaño del número más grande para la clasificación por recuento, por ejemplo).

Además, si tiene objetos que tienen un hash perfecto (o al menos un hash que mapea todos los valores de manera diferente), puede intentar usar una ordenación por conteo o por base en sus funciones hash.

Un ordenamiento Radix es particularmente adecuado para una lista vinculada, ya que es fácil hacer una tabla de punteros de cabeza correspondientes a cada valor posible de un dígito.

La ordenación por combinación no requiere acceso O (1) y es O (n ln n). Ningún algoritmo conocido para clasificar datos generales es mejor que O (n ln n).

Los algoritmos de datos especiales, como el ordenamiento por radix (limita el tamaño de los datos) o el ordenamiento por histograma (cuenta los datos discretos) podrían ordenar una lista vinculada con una función de crecimiento menor, siempre y cuando use una estructura diferente con acceso O (1) como almacenamiento temporal .

Otra clase de datos especiales es una especie de comparación de una lista casi ordenada con k elementos fuera de orden. Esto se puede ordenar en operaciones O (kn).

Copiar la lista en una matriz y viceversa sería O (N), por lo que se puede usar cualquier algoritmo de clasificación si el espacio no es un problema.

Por ejemplo, dada una lista vinculada que contiene uint_8, este código lo ordenará en tiempo O (N) usando una ordenación de histograma:

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

typedef struct _list list_t;
struct _list {
    uint8_t value;
    list_t  *next;
};


list_t* sort_list ( list_t* list )
{
    list_t* heads[257] = {0};
    list_t* tails[257] = {0};

    // O(N) loop
    for ( list_t* it = list; it != 0; it = it -> next ) {
        list_t* next = it -> next;

        if ( heads[ it -> value ] == 0 ) {
            heads[ it -> value ] = it;
        } else {
            tails[ it -> value ] -> next = it;
        }

        tails[ it -> value ] = it;
    }

    list_t* result = 0;

    // constant time loop
    for ( size_t i = 255; i-- > 0; ) {
        if ( tails[i] ) {
            tails[i] -> next = result;
            result = heads[i];
        }
    }

    return result;
}

list_t* make_list ( char* string )
{
    list_t head;

    for ( list_t* it = &head; *string; it = it -> next, ++string ) {
        it -> next = malloc ( sizeof ( list_t ) );
        it -> next -> value = ( uint8_t ) * string;
        it -> next -> next = 0;
    }

    return head.next;
}

void free_list ( list_t* list )
{
    for ( list_t* it = list; it != 0; ) {
        list_t* next = it -> next;
        free ( it );
        it = next;
    }
}

void print_list ( list_t* list )
{
    printf ( "[ " );

    if ( list ) {
        printf ( "%c", list -> value );

        for ( list_t* it = list -> next; it != 0; it = it -> next )
            printf ( ", %c", it -> value );
    }

    printf ( " ]\n" );
}


int main ( int nargs, char** args )
{
    list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" );


    print_list ( list );

    list_t* sorted = sort_list ( list );


    print_list ( sorted );

    free_list ( list );
}

No es una respuesta directa a su pregunta, pero si utiliza una lista de omisión , ya está ordenada y tiene un tiempo de búsqueda O (log N).

Como sé, el mejor algoritmo de clasificación es O (n * log n), sea cual sea el contenedor; se ha demostrado que la clasificación en el sentido amplio de la palabra (estilo mergesort / quicksort, etc.) no puede ir más abajo. Usar una lista vinculada no le dará un mejor tiempo de ejecución.

El único algoritmo que se ejecuta en O (n) es un algoritmo de "pirateo" que se basa en contar valores en lugar de ordenarlos.

Aquí hay una implementación que recorre la lista solo una vez, recopila ejecuciones y luego programa las fusiones de la misma manera que lo hace mergesort.

La complejidad es O (n log m) donde n es el número de elementos y m es el número de corridas. El mejor caso es O (n) (si los datos ya están ordenados) y el peor caso es O (n log n) como se esperaba.

Requiere memoria temporal O (log m); la clasificación se realiza en el lugar de las listas.

(actualizado a continuación. El comentarista uno hace un buen punto de que debería describirlo aquí)

La esencia del algoritmo es:

    while list not empty
        accumulate a run from the start of the list
        merge the run with a stack of merges that simulate mergesort's recursion
    merge all remaining items on the stack

La acumulación de carreras no requiere mucha explicación, pero es bueno aprovechar la oportunidad para acumular carreras ascendentes y descendentes (invertidas). Aquí antepone elementos más pequeños que el encabezado de la ejecución y agrega elementos mayores o iguales al final de la ejecución. (Tenga en cuenta que la anteposición debe usar estrictamente menor que para preservar la estabilidad de clasificación).

Es más fácil simplemente pegar el código de fusión aquí:

    int i = 0;
    for ( ; i < stack.size(); ++i) {
        if (!stack[i])
            break;
        run = merge(run, stack[i], comp);
        stack[i] = nullptr;
    }
    if (i < stack.size()) {
        stack[i] = run;
    } else {
        stack.push_back(run);
    }

Considere ordenar la lista (dagibecfjh) (ignorando las ejecuciones). Los estados de la pila proceden de la siguiente manera:

    [ ]
    [ (d) ]
    [ () (a d) ]
    [ (g), (a d) ]
    [ () () (a d g i) ]
    [ (b) () (a d g i) ]
    [ () (b e) (a d g i) ]
    [ (c) (b e) (a d g i ) ]
    [ () () () (a b c d e f g i) ]
    [ (j) () () (a b c d e f g i) ]
    [ () (h j) () (a b c d e f g i) ]

Luego, finalmente, combine todas estas listas.

Tenga en cuenta que el número de elementos (ejecuciones) en la pila [i] es cero o 2 ^ i y el tamaño de la pila está limitado por 1 + log2 (nruns). Cada elemento se fusiona una vez por nivel de pila, por lo tanto, comparaciones O (n log m). Hay una similitud pasajera con Timsort aquí, aunque Timsort mantiene su pila usando algo así como una secuencia de Fibonacci donde usa potencias de dos.

La acumulación de ejecuciones aprovecha los datos ya ordenados, de modo que en el mejor de los casos la complejidad es O (n) para una lista ya ordenada (una ejecución). Dado que estamos acumulando carreras ascendentes y descendentes, las carreras siempre tendrán al menos una longitud de 2. (Esto reduce la profundidad máxima de la pila en al menos uno, pagando el costo de encontrar las carreras en primer lugar). La complejidad del peor de los casos es O (n log n), como se esperaba, para datos muy aleatorizados.

(Um ... Segunda actualización.)

O simplemente vea wikipedia en mergesort ascendente .

Puede copiarlo en una matriz y luego ordenarlo.

• Copiando en la matriz O (n),

• sorting O (nlgn) (si usa un algoritmo rápido como merge sort),

• copiando de nuevo a la lista vinculada O (n) si es necesario,

entonces va a ser O (nlgn).

tenga en cuenta que si no conoce la cantidad de elementos en la lista vinculada, no sabrá el tamaño de la matriz. Si está codificando en Java, puede usar una Arraylist, por ejemplo.

Mergesort es lo mejor que puede hacer aquí.

La pregunta es LeetCode # 148 , y se ofrecen muchas soluciones en los principales idiomas. El mío es el siguiente, pero me pregunto sobre la complejidad del tiempo. Para encontrar el elemento del medio, recorremos la lista completa cada vez. Los nelementos de la primera vez se repiten, los 2 * n/2elementos de la segunda vez se repiten, y así sucesivamente. Parece que ha llegado el O(n^2)momento.

def sort(linked_list: LinkedList[int]) -> LinkedList[int]:
    # Return n // 2 element
    def middle(head: LinkedList[int]) -> LinkedList[int]:
        if not head or not head.next:
            return head
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

    def merge(head1: LinkedList[int], head2: LinkedList[int]) -> LinkedList[int]:
        p1 = head1
        p2 = head2
        prev = head = None

        while p1 and p2:
            smaller = p1 if p1.val < p2.val else p2
            if not head:
                head = smaller
            if prev:
                prev.next = smaller
            prev = smaller

            if smaller == p1:
                p1 = p1.next
            else:
                p2 = p2.next

        if prev:
            prev.next = p1 or p2
        else:
            head = p1 or p2

        return head

    def merge_sort(head: LinkedList[int]) -> LinkedList[int]:
        if head and head.next:
            mid = middle(head)
            mid_next = mid.next
            # Makes it easier to stop
            mid.next = None

            return merge(merge_sort(head), merge_sort(mid_next))
        else:
            return head

    return merge_sort(linked_list)