Minha ideia para solucionar seu problema é usar o quick sort para ordenar sua lista simplesmente encadeada.
Para tal, vou usar aqui uma função impl_comp
que vai comparar dois elementos da lista (vão ser passados os dados, não os nós da lista). impl_comp
pode, então, ser implementada para comparar quaisquer dois dados que se deseja, como no caso é string, vamos usar strcmp
por baixo.
Quick sort
O quick sort é um algoritmo recursivo que se baseia na seleção de um pivô, na partição dos dados e na ordenação recursiva dessa partição.
Seu algoritmo é:
quicksort(tlista *lista):
elemento pivô = seleciona_pivô(lista)
tlista *menor, *maiorigual
partição(lista, pivô, &menor, &maiorigual)
menor = quicksort(menor)
maiorigual = quicksort(maiorigual)
se pivô faz parte da lista, e não foi inserido no maiorigual:
apendar elemento pivô no final de menor
apendar maiorigual no final de menor
retorne menor
partição(tlista *lista, elemento pivô, tlista **menor_retorno, tlista **maiorigual_retorno):
tlista *atual = lista
tlista *menor_cauda = nulo
tlista *maiorigual_cauda = nulo
enquanto atual != nulo:
tlista *próximo = lista->próximo
atual->próximo = nulo
se impl_cmp(atual->valor, pivô) < 0:
// inserir na partição menor
se menor_cauda == nulo:
menor_cauda = atual
*menor_retorno = menor_cauda
senão:
menor_cauda->próximo = atual
menor_cauda = atual
senão:
// inserir na partição maior ou igual
se maiorigual_cauda == nulo:
maiorigual_cauda = atual
*maiorigual_retorno = maiorigual_cauda
senão:
maiorigual_cauda->próximo = atual
maiorigual_cauda = atual
atual = próximo
Tempo de execução
Ele tem tempo médio de execução na ordem de o(n log n)
, sendo portanto comparável com outros algoritmos de ordenação linearítmicos (linear vezes logaritmo), como merge sort e heap sort: como essa notação é assintótica, representando apenas o comportamento dominante da função de tempo de execução, não leva em consideração termos de ordem menor nem se tem alguma constante multiplicando o termo dominante.
Segundo a Wikipedia, o tempo de execução do merge sort pode ser 3 vezes mais rápido no caso médio. No pior caso, o quick sort necessita de tempo o(n^2)
operações para ser executado. Outras funções de tempo quadrático são insertion sort, selection sort e bubble sort.
Estabilidade
Um outro ponto interessante mencionar é que o quick sort não é um método de ordenação estável. Uma ordenação estável mantém a posição relativa de elementos de mesmo peso; por exemplo, se fôssemos ordenar por ordem alfabética, ignorando o caso, e tivéssemos como entrada "ana", "jeff", "Ana"
, uma ordenação estável produziria necessariamente "ana", "Ana", "jeff"
, mas talvez a saída do quick sort seja "Ana", "ana", "jeff"
.
Saber se ordenações são estáveis é interessante quando se deseja organizar por múltiplos fatores distintos. Um caso desse tipo de ordenação poderia ser aplicado aqui no Stack Overflow em português (exemplo didático, não necessariamente prático): ordene as pessoas por ordem de pontos e, em caso de empate, priorize os mais recentes.
Para realizar essa ordenação, poderíamos usar uma ordenação por mais recentes e, depois, uma ordenação estável por pontos; como ordenamos inicialmente por mais recentes, a ordenação estável manterá essa ordem parcial quando for fazer a ordenação final.
E essa brincadeira em C, como fica?
Primeiramente, quero construir com um nível de abstração aqui. Onde eu colocar elemento
troque para o tipo realmente sendo usado. No presente caso, seria char*
, por ser comparação de string. Em segundo lugar, estou postergando a implementação de impl_cmp(elemento a, elemento b)
para que se possa usar a implementação adequada de comparação.
/* substitua "elemento" pelo tipo de dado utilizado */
typedef struct lista {
elemento valor;
struct lista *prox;
} tlista;
/* não se esqueça de implementar essa função */
int impl_cmp(elemento a, elemento b);
/* l_ret: retorno menor/lesser
* ge_ret: retorno maior ou igual/greater equal
*/
void partition(tlista *lista, elemento pivot, tlista **l_ret, tlista **ge_ret) {
tlista *l_tail = NULL;
tlista *ge_tail = NULL;
tlista *atual = lista;
while (atual != NULL) {
tlista *prox = atual->prox;
atual->prox = NULL;
if (impl_cmp(atual->valor, pivot) < 0) {
if (l_tail == NULL) {
l_tail = atual;
*l_ret = l_tail;
} else {
l_tail->prox = atual;
l_tail = atual;
}
} else {
if (ge_tail == NULL) {
ge_tail = atual;
*ge_ret = ge_tail;
} else {
ge_tail->prox = atual;
ge_tail = atual;
}
}
atual = prox;
}
}
tlista *concatena_3_listas(tlista *a, tlista *b, tlista *c) {
tlista *head = a;
tlista *tail = head;
if (head != NULL) {
head = tail = b;
} else {
while (tail->prox != NULL) {
tail = tail->prox;
}
tail->prox = b;
}
if (head != NULL) {
head = tail = c;
} else {
while (tail->prox != NULL) {
tail = tail->prox;
}
tail->prox = c;
}
return head;
}
tlista *quicksort(tlista *lista) {
/* vou pegar como pivot sempre o primeiro da lista, removendo-o de lá; poderia usar outra técnica, mas essa é boa o suficiente para o exemplo */
tlista *pivot_lista = lista;
elemento pivot = pivot_lista->valor;
lista = lista->prox;
pivot_lista->prox = NULL;
tlista *menor, *maior;
menor = maior = NULL;
partition(lista, pivot, &menor, &maior);
menor = quicksort(menor);
maior = quicksort(maior);
return concatena_3_listas(menor, pivot_lista, maior);
}
Notas sobre a comparação com a implementação sobre vetor
Quando se usa o quicksort in loco em um vetor, sempre se envia para as funções recursivas qual o começo e qual o fim de cada conjunto de elementos nas chamadas recursivas de partição e de quicksort. Também, quando o pivô faz parte do vetor, faz-se um último swap do último elemento do subvetor de elementos menores com o pivô (que normalmente fica na primeira posição do vetor; se ele ficar na última, troca-se com o primeiro elemento do subvetor de elementos maiores ou iguais).
Como a estrutura de dados de lista simplesmente encadeada traz consigo a noção de começo (o ponteiro da lista é o começo dela mesma) e de fim (último elemento existente cujo próximo elemento é nulo), não é necessário ficar passando essa informação adiante.
ordenacao()
podes precisar de alterar o*primeiro
mas não tens nenhuma instrução que faça isso.