7

Eu preciso ordenar uma lista encadeada (implementação própria, sem utilizar API do Java) com um método de ordenação que possua complexidade O(n*log(n)). Pesquisando métodos que satisfaçam a condição encontrei o quicksort, entretanto, ele pressupõe acesso randômico aos elementos que serão ordenados, o que é inviável no caso da lista.
Assim, tive a ideia de copiar todos os elementos da minha lista para um vetor, realizar a ordenação com quicksort e copiá-los novamente para a lista depois de ordenados. Essa solução é viável? Ela é capaz de manter a complexidade desejada? Além disso, existem outros métodos com essa mesma complexidade que se adequem mais à lista encadeada?

3 Respostas 3

3

Baseado na tabela linkada pelo @Maniero, há pelo menos 4 algoritmos de ordenação que, na média, são de complexidade O(n*log(n)), a saber:

  • Quicksort
  • Mergesort
  • Timsort
  • Heapsort

Copiar os dados para um array pode ser uma opção

A página do Heapsort na Wikipédia diz:

Merge sort can be adapted to operate on singly linked lists with O(1) extra space. Heapsort can be adapted to operate on doubly linked lists with only O(1) extra space overhead.

Traduzindo:

Mergesort pode ser adaptado para funcionar em listas singularmente encadeadas com espaço extra O(1). Heapsort pode ser adaptado para funcionar em listas duplamente encadeadas com aumento do espaço extra de apenas O(1).

Infelizmente não tem exemplo nem referência. Como fazer isso? Basicamente você pode trocar o acesso aleatório de vetor por referências aos elementos da lista encadeada.

No caso do Heap sort, o algoritmo da Wikipédia tem um trecho assim:

end ← count - 1
while end > 0 do
    (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
    swap(a[end], a[0])
    (the heap size is reduced by one)
    end ← end - 1
    (the swap ruined the heap property, so restore it)
    siftDown(a, 0, end)

Então, por exemplo, aonde há incremento ou decremento, basta substituir isso por um avanço ou retrocesso na lista. Onde há referência ao primeiro elemento, usa-se uma referência ao primeiro, o mesmo se faz com o último.

Exemplo:

procedure heapsort(first, last, count) is
    input: first and last elements of a doubly linked list with length of count

    heapify(first, last, count)
    end ← last
    while end.previous != null do
        swap(end, first)
        end ← end.previous
        count ← count - 1
        siftDown(first, end, count)


procedure heapify(first, last, count) is
    start ← iParent(first, count)
    while start != null do
        siftDown(start, last, count - 1)
        start ← start.previous
        count ← count - 1


procedure siftDown(start, end, count) is
    root ← start
    while iLeftChild(start, root, count) ≤ end do 
        child ← iLeftChild(start, root, count)
        swap ← root     
        if swap.value < child.value
            swap ← child
        if child.next.value ≤ end.value and swap.value < child.next.value
            swap ← child.next
        if swap.value = root.value
            return
        else
            swap(root, swap)

Note que no meu exemplo acima, cada elemento (first, last, start, end, root, swap) agora é na verdade uma referência que contém 3 atributos: value, previous e next.

Ainda resta implementar as rotinas iParent(start, count) e iLeftChild(start, end, count).

  • iParent basicamente precisa encontrar o elemento central. Isso não é trivial em listas encadeadas, mas pode ser facilmente implementado já que temos a referência ao primeiro elemento e a quantidade. Tudo o que precisa ser feito é avançar floor((count-1) / 2) vezes a partir do primeiro elemento.
  • iLeftChild basicamente avança 2*i + 1, sendo i a posição do elemento root em relação à start. Então pode ser facilmente implementado avançando uma referência count + 1 vezes a partir de root.

Isso funciona? Deveria, mas não testei. Implemente por sua conta e risco, considerando que as rotinas de busca descritas acima vão deixar o algoritmo um pouquinho mais lento, embora eu acredite que outras formas de otimização podem ser encontradas.

3

A pergunta é de algo que pode garantir a complexidade, não fala em nada relacionado com a velocidade, são conceitos diferentes.

Lista encadeada com essa complexidade é difícil encontrar, só quicksort não consegue esta complexidade. Copiando antes só piora a situação.

Copiar para outra estrutura pode dar mais velocidade, mas não dar esta complexidade.

Parece que alguém conseguiu fazer com mergesort, mas sem copiar nada antes :) A resposta aceita em pergunta no SO fala justamente desta solução.

O mergesort, assim como o heapsort, conseguem dar a complexidade exigida na pergunta. Estes são dois algoritmos bem conhecidos, claro que depende um pouco da implementação. O problema destes dois algoritmos é que ele consome muito espaço - O(N). A pergunta não fala nada em espaço, mas especificamente por ser uma lista ligada, estes algoritmos conseguem O(1).

Dá uma olhada no Radix, ele costuma operar milagres, mas é difícil implementar.

Essa tabela pode ajudar ainda que não seja específico para linked list, o algoritmo implementado adequadamente pode garantir a complexidade exigida.

Coloquei no GitHub para referência futura.

0

Copiar pode não ser uma má ideia.

O(n*log n + n) para um n suficientemente grande pode ser considerado o mesmo que O(n*log(n)).

Note, entretanto, que a notação Big-O é um direcionamento muito importante, mas não definitivo no momento de fazer análises práticas de algoritmos. Existem vários detalhes de otimização de hardware que não são levados em conta em uma análise puramente Big-O.

1
  • O Downvoter poderia sinalizar, por favor, o problema que viu na resposta?
    – cantoni
    3/02/2016 às 9:30

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .