How to order a chained list in alphabetical order?

Question

I have to make a program that creates a chained list containing structs with information from a participant(name, Cpf...). I have already inserted the function and I want to sort the chained list in another function called sorting.

But the program gives when executing the ordering or does not execute it right. I’ve searched several sites but could not find answer to the solution of my problem.

void ordenacao(participante **primeiro, int tam)
{
    int i = 0, retorno;
    participante *anterior, *proximo, *aux, *aux2;

    if(tam > 1)
    {
            anterior = *primeiro;
            proximo = anterior->prox;

            while(proximo!=NULL)
            {
                    retorno = strcmp(anterior->nome, proximo->nome);

                   if(retorno > 0)
                   {
                        aux = anterior;
                        aux2 = proximo;
                        anterior->prox = proximo->prox;
                        proximo->prox = aux;
                        printf("Retorno = %d\n", retorno);
                   }
           i++;
           anterior = anterior->prox;
           proximo = proximo->prox;
           }
      }


system("pause");
}

Answer 1

My idea to solve your problem is to use Quick Sort to sort your list simply chained.

So I’m going to use a function here impl_comp which will compare two elements of the list (data will be passed, not list nodes). impl_comp can then be implemented to compare any two data you want, as in the case is string, we will use strcmp underneath.

Quick Sort

Quick Sort is a recursive algorithm based on the selection of a pivot, the partition of the data and the recursive ordering of that partition.

Its algorithm is:

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

Running time

It has average run time in the order of o(n log n), is therefore comparable to other linear ordering algorithms (linear times logarithm), such as merge Sort and heap Sort: as this notation is asymptotic, representing only the dominant behavior of the runtime function, does not take into account terms of minor order nor does it have any constant multiplying the dominant term.

According to Wikipedia, merge time can be 3 times faster in the average case. In the worst case, Quick Sort needs time o(n^2) operations to be executed. Other quadratic time functions are Insertion Sort, Selection Sort and Bubble Sort.

Stability

Another interesting point to mention is that Quick Sort is not a sorting method stable. A stable ordering maintains the relative position of elements of the same weight; for example, if we were to sort alphabetically, ignoring the case, and had as input "ana", "jeff", "Ana", a stable ordering would necessarily produce "ana", "Ana", "jeff", but maybe the output of Quick Sort is "Ana", "ana", "jeff".

Knowing whether the sorts are stable is interesting when you want to organize by multiple different factors. A case of this sort of ordering could be applied here in the Stack Overflow in Portuguese (didactic example, not necessarily practical): order people in order of points and, in case of a tie, prioritize the most recent.

To accomplish this ordering, we could use a more recent ordering and then a stable ordering by points; as we ordered initially by more recent, the stable ordering will maintain this partial order when making the final ordering.

And this joke in C, as it turns out?

First, I want to build with a level of abstraction here. Where do I put elemento change to the type actually being used. In the present case, it would be char*, for being string comparison. Secondly, I am postponing the implementation of impl_cmp(elemento a, elemento b) so that appropriate comparison implementation can be used.

/* 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);
}

Notes on comparison with vector implementation

When using the quicksort in loco In an array, one always sends to the recursive functions which the beginning and the end of each set of elements in recursive partition and quicksort calls. Also, when the pivot is part of the vector, a last swap of the last element of the minor element subvector with the pivot (which normally is in the first position of the vector; if it is in the last, it is exchanged with the first element of the large or equal element subvector).

Since the simply chained list data structure brings with it the notion of beginning (the pointer of the list is the beginning of itself) and end (the last existing element whose next element is null), it is not necessary to keep passing this information on.

Answer 2

You need two loops to work, the algorithm is the Bubble Sort;

void ordenar(lista **l) {

    if(*l == NULL || (*l)->prox == NULL) return; //se for nulo(vazio), ou apenas 1 elemento
    lista *aux = *l, *t;
    char s[100]; //precisa de espacao suficiente para armazenar o nome

    while(aux != NULL) {
      t = aux->prox;
      while(t != NULL) {
        if(strcmp(aux->nome, t->nome) > 0) { //se vir depois
            strcpy(s, aux->nome);
            strcpy(aux->nome, t->nome);
            strcpy(t->nome, s);
        }
        t = t->prox;
      }
      aux = aux->prox;
    }
}

http://ideone.com/nidDTe