Sort linked list in C

Ordering with copy of values

The simplest way to demonstrate this for the code you have is through an bubble sort algorithm with the copy of the values of each structure between them. The difference is mostly in the list, which is done through the proximo pointers.

Implementation:

Dado *pessoa1 = inicio;

while (pessoa1 != NULL){
    Dado *pessoa2 = pessoa1->proximo;
    while (pessoa2 != NULL){
        if (pessoa1->idade > pessoa2->idade){ //se maior troca o conteudo das duas pessoas
            int temp_idade = pessoa1->idade; 
            pessoa1->idade = pessoa2->idade;
            pessoa2->idade = temp_idade;
            troca_string(pessoa1->CPF, pessoa2->CPF, 12);
            troca_string(pessoa1->nome, pessoa2->nome, 41);
            troca_string(pessoa1->email, pessoa2->email, 31);
        }
        pessoa2 = pessoa2->proximo;
    }

    pessoa1 = pessoa1->proximo;
}

The first while cycles through the list from start to finish, and the second while will go further, and every time you find a person of a greater age, you change all of that person's values. Since there are several strings to be exchanged I chose to create a function that makes the exchange of string up to a certain amount of characters in order to simplify. Since there was only one field of the integer type to be exchanged I did no function for this exchange.

The function troca_string would be:

void troca_string(char *str1, char *str2, size_t tamanho){
    static char temp[50];
    memcpy(temp, str1, tamanho);
    memcpy(str1, str2, tamanho);
    memcpy(str2, temp, tamanho);
}

In this case, static prevents the temp string from being created every time the function is called, and is created only once, which is ideal for this scenario. For the exchange of the string itself I used the memcpy function that already exists to copy the whole string, but could have done the same at the expense of a normal loop copying letter to letter.

This implementation in spite of working is not very good because the exchange of each element of the structure is very heavy. On my machine sizeof(Dado) gives 92, which is 92 bytes, which means that each switch has to copy 92 bytes 3 times. And it can still be worse depending on the quantity and size of the fields of the structure, as well as the quantity of elements to order. The solution to this problem is pointers.

Sorting by pointer switching

With change of pointers we can avoid copying the various values, but this solution usually means changing the original structure and consequently a lot of the code and so it becomes a little annoying.

In this case the structure would have a pointer to the data and another to the next node in the list as it already had:

typedef struct Info { //informação de cada pessoa
    char CPF[12];
    char nome[41];
    char email[31];
    int idade;
} Info;

typedef struct Dado {
    Info* info; //agora ponteiro em vez de os campos diretamente
    struct Dado* proximo;
} Dado;

The structure Dado actually corresponds to each node in the list whereas the Info structure corresponds to each person's information.

With this change the reading of the file information would have to be different because not only must it also allocate space for the Info as the read must become on the Info :

int main() {
    ... 
    Dado *inicio = NULL, *fim = NULL;

    while (1) {
        Dado *pessoa = malloc(sizeof(Dado));
        pessoa->info = malloc(sizeof(Info)); //alocar também o info

        pessoa->proximo = NULL;
        if (inicio == NULL) {
            inicio = pessoa;
        }
        if (fim != NULL) {
            fim->proximo = pessoa;
        }

        if (ler_string_arq(arq, pessoa->info->CPF)) { //agora ->info->CPF
            free(pessoa->info); //liberar tambem o info
            free(pessoa);
            fim->proximo = NULL;
            break;
        }
        fim = pessoa;

        ler_string_arq(arq, pessoa->info->nome); //->info->nome
        ler_string_arq(arq,pessoa->info->email); //->info->email
        fscanf(arq,"%d", &pessoa->info->idade); //->info->idade
        fscanf(arq,"%c", &ch);
    }
    fclose(arq);

The ordering is now simpler and more efficient because when it is necessary to change two people of order, just change the pointer to the information of each node:

Dado *pessoa1 = inicio;

while (pessoa1 != NULL){
    Dado *pessoa2 = pessoa1->proximo;
    while (pessoa2 != NULL){
        if (pessoa1->info->idade > pessoa2->info->idade){
            Info *temp = pessoa1->info; //agora troca só o info
            pessoa1->info = pessoa2->info;
            pessoa2->info = temp;
        }
        pessoa2 = pessoa2->proximo;
    }

    pessoa1 = pessoa1->proximo;
}

The show also has to switch to ->info :

arqout = fopen("write.txt","w");
Dado* pessoa = inicio;
while (pessoa != NULL) {
    fprintf(arqout,"%s,%s,%s,%d\n", pessoa->info->CPF, pessoa->info->nome, pessoa->info->email, pessoa->info->idade);
    pessoa= pessoa->proximo;
}
fclose(arqout);

Complete code for reference:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Info {
    char CPF[12];
    char nome[41];
    char email[31];
    int idade;
} Info;

typedef struct Dado {
    Info* info;
    struct Dado* proximo;
} Dado;

int ler_string_arq(FILE* arq, char *campo_destino) {
    int letra = 0;
    char ch;
    if (fscanf(arq,"%c",&ch) == EOF) {
        return 1;
    }
    while( ch != ',') {
        campo_destino[letra] = ch;
        fscanf(arq,"%c", &ch);
        letra++;
    }
    campo_destino[letra] = '
Dado *pessoa1 = inicio;

while (pessoa1 != NULL){
    Dado *pessoa2 = pessoa1->proximo;
    while (pessoa2 != NULL){
        if (pessoa1->idade > pessoa2->idade){ //se maior troca o conteudo das duas pessoas
            int temp_idade = pessoa1->idade; 
            pessoa1->idade = pessoa2->idade;
            pessoa2->idade = temp_idade;
            troca_string(pessoa1->CPF, pessoa2->CPF, 12);
            troca_string(pessoa1->nome, pessoa2->nome, 41);
            troca_string(pessoa1->email, pessoa2->email, 31);
        }
        pessoa2 = pessoa2->proximo;
    }

    pessoa1 = pessoa1->proximo;
}
';
    return 0;
}

int main() {
    FILE *arq, *arqout;
    char ch,teste;

    arq = fopen("read.txt","r");

    Dado *inicio = NULL, *fim = NULL;

    while (1) {
        Dado *pessoa = malloc(sizeof(Dado));
        pessoa->info = malloc(sizeof(Info));

        pessoa->proximo = NULL;
        if (inicio == NULL) {
            inicio = pessoa;
        }
        if (fim != NULL) {

            fim->proximo = pessoa;
        }

        if (ler_string_arq(arq, pessoa->info->CPF)) {
            free(pessoa->info);
            free(pessoa);
            fim->proximo = NULL;
            break;
        }
        fim = pessoa;

        ler_string_arq(arq, pessoa->info->nome);
        ler_string_arq(arq,pessoa->info->email);
        fscanf(arq,"%d", &pessoa->info->idade);
        fscanf(arq,"%c", &ch);
    }
    fclose(arq);

    Dado *pessoa1 = inicio;

    while (pessoa1 != NULL){
        Dado *pessoa2 = pessoa1->proximo;
        while (pessoa2 != NULL){
            if (pessoa1->info->idade > pessoa2->info->idade){
                Info *temp = pessoa1->info;
                pessoa1->info = pessoa2->info;
                pessoa2->info = temp;
            }
            pessoa2 = pessoa2->proximo;
        }

        pessoa1 = pessoa1->proximo;
    }

    arqout = fopen("write.txt","w");
    Dado* pessoa = inicio;
    while (pessoa != NULL) {
        fprintf(arqout,"%s,%s,%s,%d\n", pessoa->info->CPF, pessoa->info->nome, pessoa->info->email, pessoa->info->idade);
        pessoa= pessoa->proximo;
    }
    fclose(arqout);
    return 0;
}