Eu estou trabalhando na implementação de uma função de quicksort para classificar listas ligadas individualmente. Qual algoritmo eu teria que usar para conseguir isso? Para uma lista encadeada, seria necessário o pior caso O (N) para cada comparação, em vez do O (1) usual para matrizes. Então, qual seria o pior caso de complexidade?

Para resumir, que modificações preciso fazer no algoritmo de quicksort para ter um algoritmo de ordenação ideal e qual seria a pior complexidade do algoritmo?

Obrigado!

Eu tenho uma implementação abaixo:

public static SingleLinkedList quickSort(SingleLinkedList list, SLNode first, SLNode last)
{
    if (first != null && last != null)
    {
        SLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SinlgleLinkedList list, SLNode first, SLNode last)
{

    SLNode p = first ;
    SLNode ptr = p.succ ;

    while (ptr!=null)
    {
        if (ptr.data.compareToIgnoreCase(p.data)<0)
        {
            String pivot = p.data ;
            p.data =  ptr.data ;
            ptr.data = p.succ.data ;
            p.succ.data = pivot ;
            p = p.succ ;
        }
        ptr = ptr.succ ;
    }
    return p ;
}