Qual é o algoritmo mais rápido para classificar uma lista vinculada?

Estou curioso para saber se O (n log n) é o melhor que uma lista vinculada pode fazer.

É razoável esperar que você não possa fazer nada melhor do que O (N log N) em tempo de execução .

No entanto, a parte interessante é investigar se você pode classificá-lo no local , de forma estável , seu comportamento de pior caso e assim por diante.

Simon Tatham, famoso pelo Putty, explica como classificar uma lista vinculada com a classificação por mesclagem . Ele conclui com os seguintes comentários:

Como qualquer algoritmo de classificação que se preze, este tem tempo de execução O (N log N). Por ser Mergesort, o pior caso de tempo de execução ainda é O (N log N); não há casos patológicos.

O requisito de armazenamento auxiliar é pequeno e constante (ou seja, algumas variáveis ​​na rotina de classificação). Graças ao comportamento inerentemente diferente de listas vinculadas de matrizes, essa implementação de Mergesort evita o custo de armazenamento auxiliar O (N) normalmente associado ao algoritmo.

Há também um exemplo de implementação em C que funciona tanto para listas simples quanto duplamente vinculadas.

Como @ Jørgen Fogh menciona abaixo, a notação big-O pode ocultar alguns fatores constantes que podem fazer com que um algoritmo tenha um desempenho melhor devido à localidade da memória, devido a um baixo número de itens, etc.

Dependendo de vários fatores, pode ser mais rápido copiar a lista para um array e então usar um Quicksort .

O motivo pelo qual isso pode ser mais rápido é que um array tem um desempenho de cache muito melhor do que uma lista vinculada. Se os nós da lista estiverem dispersos na memória, você pode estar gerando perdas de cache em todos os lugares. Então, novamente, se o array for grande, você terá falhas de cache de qualquer maneira.

Mergesort paraleliza melhor, então pode ser uma escolha melhor se for isso o que você deseja. Também é muito mais rápido se você executá-lo diretamente na lista vinculada.

Como os dois algoritmos são executados em O (n * log n), tomar uma decisão informada envolveria o perfil de ambos na máquina em que você gostaria de executá-los.

--- EDITAR

Decidi testar minha hipótese e escrevi um programa C que mede o tempo (usando clock()) gasto para classificar uma lista vinculada de ints. Eu tentei com uma lista vinculada onde cada nó foi alocado commalloc() e uma lista vinculada onde os nós foram dispostos linearmente em uma matriz, para que o desempenho do cache fosse melhor. Eu os comparei com o qsort embutido, que incluía copiar tudo de uma lista fragmentada para um array e copiar o resultado de volta. Cada algoritmo foi executado nos mesmos 10 conjuntos de dados e os resultados foram calculados.

Estes são os resultados:

N = 1000:

Lista fragmentada com classificação por mesclagem: 0,000000 segundos

Matriz com qsort: 0,000000 segundos

Lista compactada com classificação por mesclagem: 0,000000 segundos

N = 100000:

Lista fragmentada com classificação por mesclagem: 0,039000 segundos

Matriz com qsort: 0,025000 segundos

Lista compactada com classificação por mesclagem: 0,009000 segundos

N = 1000000:

Lista fragmentada com classificação por mesclagem: 1,162000 segundos

Matriz com qsort: 0,420000 segundos

Lista compactada com classificação por mesclagem: 0,112000 segundos

N = 100000000:

Lista fragmentada com classificação por mesclagem: 364,797000 segundos

Matriz com qsort: 61,166000 segundos

Lista compactada com classificação por mesclagem: 16,525000 segundos

Conclusão:

Pelo menos na minha máquina, copiar em um array vale a pena para melhorar o desempenho do cache, já que você raramente tem uma lista encadeada completamente compactada na vida real. Deve-se notar que minha máquina possui um Phenom II de 2,8 GHz, mas apenas 0,6 GHz de RAM, então o cache é muito importante.

As classificações de comparação (ou seja, aquelas baseadas na comparação de elementos) não podem ser mais rápidas do que n log n. Não importa qual seja a estrutura de dados subjacente. Veja a Wikipedia .

Outros tipos de tipo que tiram vantagem da existência de muitos elementos idênticos na lista (como o tipo de contagem) ou alguma distribuição esperada de elementos na lista são mais rápidos, embora eu não consiga pensar em nenhum que funcione particularmente bem em uma lista vinculada.

Este é um pequeno artigo interessante sobre este tópico. Sua conclusão empírica é que Treesort é o melhor, seguido por Quicksort e Mergesort. A classificação de sedimentos, a classificação de bolhas e a classificação por seleção têm um desempenho muito ruim.

UM ESTUDO COMPARATIVO DE ALGORITMOS DE CLASSIFICAÇÃO DE LISTA VINCULADA por Ching-Kuang Shene

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

Como afirmado muitas vezes, o limite inferior na classificação baseada em comparação para dados gerais será O (n log n). Para resumir brevemente esses argumentos, existem n! maneiras diferentes de ordenar uma lista. Qualquer tipo de árvore de comparação que tenha n! (que está em O (n ^ n)) possíveis classificações finais vão precisar de pelo menos log (n!) como sua altura: isso dá a você um limite inferior O (log (n ^ n)), que é O (n log n).

Assim, para dados gerais em uma lista encadeada, a melhor classificação possível que funcionará em quaisquer dados que possam comparar dois objetos será O (n log n). No entanto, se você tiver um domínio mais limitado de coisas para trabalhar, pode melhorar o tempo que leva (pelo menos proporcional an). Por exemplo, se você estiver trabalhando com números inteiros não maiores do que algum valor, você pode usar Classificação por contagem ou Classificação por raiz , pois eles usam os objetos específicos que você está classificando para reduzir a complexidade com proporção para n. No entanto, tenha cuidado, pois isso adiciona algumas outras coisas à complexidade que você pode não considerar (por exemplo, Classificação por contagem e classificação por raiz adicionam fatores que são baseados no tamanho dos números que você está classificando, O (n + k ) onde k é o tamanho do maior número para Classificação por contagem, por exemplo).

Além disso, se acontecer de você ter objetos que têm um hash perfeito (ou pelo menos um hash que mapeia todos os valores de forma diferente), você pode tentar usar uma contagem ou classificação raiz em suas funções hash.

Uma classificação Radix é particularmente adequada para uma lista vinculada, uma vez que é fácil fazer uma tabela de ponteiros principais correspondendo a cada valor possível de um dígito.

A classificação por mesclagem não requer acesso O (1) e é O (n ln n). Nenhum algoritmo conhecido para classificar dados gerais é melhor do que O (n ln n).

Os algoritmos de dados especiais, como classificação por raiz (limita o tamanho dos dados) ou classificação por histograma (conta dados discretos) podem classificar uma lista vinculada com uma função de crescimento inferior, contanto que você use uma estrutura diferente com acesso O (1) como armazenamento temporário .

Outra classe de dados especiais é um tipo de comparação de uma lista quase classificada com k elementos fora de ordem. Isso pode ser classificado em operações O (kn).

Copiar a lista para um array e vice-versa seria O (N), portanto, qualquer algoritmo de classificação pode ser usado se o espaço não for um problema.

Por exemplo, dada uma lista vinculada contendo uint_8, este código irá classificá-la no tempo O (N) usando uma classificação 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 );
}

Não é uma resposta direta à sua pergunta, mas se você usar uma Lista de Pulos , ela já está classificada e tem tempo de pesquisa O (log N).

Como eu sei, o melhor algoritmo de classificação é O (n * log n), qualquer que seja o contêiner - foi provado que a classificação no sentido amplo da palavra (estilo mergesort / quicksort etc.) não pode ser inferior. Usar uma lista vinculada não proporcionará um melhor tempo de execução.

O único algoritmo que roda em O (n) é um algoritmo de "hack" que se baseia na contagem de valores ao invés de classificação.

Aqui está uma implementação que percorre a lista apenas uma vez, coletando execuções e, a seguir, programa as mesclagens da mesma maneira que mergesort.

A complexidade é O (n log m), onde n é o número de itens em é o número de execuções. O melhor caso é O (n) (se os dados já estiverem classificados) e o pior caso é O (n log n) conforme esperado.

Requer O (log m) de memória temporária; a classificação é feita no local nas listas.

(atualizado abaixo. o comentarista um faz questão de que eu deveria descrevê-lo aqui)

A essência do algoritmo é:

    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

O acúmulo de corridas não requer muita explicação, mas é bom aproveitar a oportunidade para acumular corridas ascendentes e descidas (invertidas). Aqui, ele adiciona itens menores que o início da corrida e itens maiores ou iguais ao final da corrida. (Observe que o prefixo deve usar estritamente menor que para preservar a estabilidade da classificação.)

É mais fácil apenas colar o código de mesclagem aqui:

    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 classificar a lista (dagibecfjh) (ignorando execuções). Os estados da pilha procedem da seguinte forma:

    [ ]
    [ (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) ]

Então, finalmente, mescle todas essas listas.

Observe que o número de itens (execuções) na pilha [i] é zero ou 2 ^ i e o tamanho da pilha é limitado por 1 + log2 (nruns). Cada elemento é mesclado uma vez por nível de pilha, portanto, comparações O (n log m). Há uma semelhança passageira com Timsort aqui, embora Timsort mantenha sua pilha usando algo como uma sequência de Fibonacci em que usa potências de dois.

A acumulação de execuções tira proveito de quaisquer dados já classificados, de forma que a complexidade do melhor caso seja O (n) para uma lista já classificada (uma execução). Como estamos acumulando corridas ascendentes e descendentes, as corridas sempre terão pelo menos 2. (Isso reduz a profundidade máxima da pilha em pelo menos um, pagando pelo custo de encontrar as corridas em primeiro lugar.) O pior caso de complexidade é O (n log n), conforme esperado, para dados altamente aleatórios.

(Hum ... Segunda atualização.)

Ou apenas veja a Wikipedia em mergesort ascendente .

Você pode copiá-lo em uma matriz e classificá-lo.

• Copiando na matriz O (n),

• classificação O (nlgn) (se você usar um algoritmo rápido como classificação por mesclagem),

• copiando de volta para a lista vinculada O (n) se necessário,

então vai ser O (nlgn).

observe que, se você não souber o número de elementos na lista vinculada, não saberá o tamanho do array. Se você está programando em java, pode usar um Arraylist, por exemplo.

Mergesort é o melhor que você pode fazer aqui.

A questão é LeetCode # 148 , e existem muitas soluções oferecidas em todos os principais idiomas. O meu é o seguinte, mas estou me perguntando sobre a complexidade do tempo. Para encontrar o elemento do meio, percorremos a lista completa todas as vezes. Os nelementos da primeira vez são iterados, os 2 * n/2elementos da segunda vez são iterados, e assim por diante. Parece que está na O(n^2)hora.

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)