Can a linked list be sorted by changing the references?

Question

I'm trying to sort a linked list using bubble sort algorithm, by changing the references of nodes. I have searched through a lot of books and on the internet, but I have only found sort methods that changes the values from the information part between nodes. What I want to do is sorting by changing the order of traveling the list, not the values between them. Here's my code. PS: The sort algorithm does not work. It's not duplicate of merge sort list, because it's entirely another algorithm.

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define LINESIZE 128
struct Student {
    float medie;
    char nrMatricol[10];
    char *nume;
    char facltate[6];
};
struct Nod{
    Student stud;
    Nod* next;
};
Nod* inserareNodEnd(Nod *l,Student st)
{
    Nod *nou = (Nod*)malloc(sizeof(Nod));
    nou->next = NULL;//NOU->NEXT=0
    nou->stud = st;
    if (!l) {
        //lista este goala
        return nou;
    }
    else
    {
     //lista contine un nod
        Nod *t = l;
        while (t->next) {
            t = t->next;
        }
        t->next = nou;
        return l;
    }

}
float medieStudenti(Nod *lista) {
    float suma=0;
    int i=0;
    Nod *aux=lista;
    while (aux->next) {
        aux = aux->next;
        suma += aux->stud.medie;
        i++;
    }
    return suma/i;
}
Nod *stergerePrimulNodLista(Nod *l,Student *st) {
    if (l) {
        Nod *aux = l;
        l = l->next;
        aux->next = NULL;
        *st = aux->stud;
        //aux->next = NULL;
        free(aux);

    }
        return l;
}
Nod* sortareLista(Nod *l) {
    Nod *i=l;
    Nod *j=l;
    Nod *aux=l;
    Nod *min=l;
    min = i;
    while (i->next) {

        if (i->stud.medie < min->stud.medie) {
            min = i;
        }
        i = i->next;

    }
    i = l;
    int n = 0;
    while (i->next) {
        j = i->next;
        while (j->next) {
            if (i->stud.medie > j->stud.medie) {
                aux = i->next;
                i->next = j->next;
                j->next = aux;
            }
            j = j->next;
        }
        i = i->next;
    }

    return min;
    //return l;
}
void dezalocare(Nod *lista) {
    Nod *aux;
    aux = lista;
    while (aux->next) {
        lista = aux->next;
        free(aux->stud.nume);
        free(aux);
        aux = lista;
    }
}
void main()
{
    FILE *f;
    Student s;
    Nod *list=NULL;
    f = fopen("fisier.txt", "r");
    char fileBuff[LINESIZE], SEPARATORI[] = { "," };
    char *token;
    while (fgets(fileBuff, LINESIZE, f)) {
        token = strtok(fileBuff, SEPARATORI);
        strcpy(s.nrMatricol, token);
        //extragere token nume student din aceeasi linie
        //salvata in file Buff
        token = strtok(NULL, SEPARATORI);
        s.nume = (char*)malloc(sizeof(char)*strlen(token) + 1);
        strcpy(s.nume, token);
        token = strtok(NULL, SEPARATORI);
        strcpy(s.facltate, token);
        //extragere tokeni medie si conversia tokenului la float
        token = strtok(NULL, SEPARATORI);
        s.medie = atof(token);
        list = inserareNodEnd(list, s);
        printf("%s %s \n", s.nrMatricol, s.nume);
    }
    Nod *tmp = list;
    while (tmp) {
        printf("\nSe afiseaza din lista");
        printf("%s %s \n", tmp->stud.nrMatricol, tmp->stud.nume);
        tmp = tmp->next;
    }

    fclose(f);
    //determinarea mediei pentru studentii din lista
    float media = medieStudenti(list);
    printf("\nMedia este %.2f", media);
    //sortare lista dupa medie(cu modificarea adreselor de legatura)

    //tema dezalocare lista
    //tema dezalocari la nivel de aplicatie
    printf("\nAcesta este Ionel %s %s \n", s.nrMatricol, s.nume);
//  list = stergerePrimulNodLista(list, &s);
    tmp = list;
    while (tmp) {
        printf("\nSe afiseaza din lista");
        printf("%s %s \n", tmp->stud.nrMatricol, tmp->stud.nume);
        tmp = tmp->next;
    }

     tmp = list;
    while (tmp) {
        printf("\nSe afiseaza  lista sortata");
        printf("%s %s \n", tmp->stud.nrMatricol, tmp->stud.nume);
        tmp = tmp->next;
    }
    dezalocare(list);
  }

Answer 1

As requested by original poster, example of a bubble sort for linked list.

Update - removed swap, using pnEnd (ptr to end of unsorted list) instead.

/* bubble sort linked list */

NODE * SortList(NODE *pHead)    /* pHead used as local ptr to start of list */
{
NODE *pEnd = NULL;              /* ptr to end of unsorted part of list */
NODE *pnEnd;                    /* pEnd for next pass */
NODE *pNext;                    /* ptr to next node */
NODE **ppCurr;                  /* ptr to ptr to curr node */
    if(pHead == NULL)           /* return if empty list */
        return pHead;
    do{
        ppCurr = &pHead;        /* set ppCurr to start of list */
        pnEnd = pHead->next;    /* set pnEnd to 2nd node */
        while((pNext = (*ppCurr)->next) != pEnd){
            if((*ppCurr)->data > pNext->data){ /* if out of order swap */
                (*ppCurr)->next = pNext->next;
                pnEnd = pNext->next = *ppCurr;
                *ppCurr = pNext;
            }
            ppCurr = &(*ppCurr)->next;
        }
        pEnd = pnEnd;           /* update pEnd since rest of list is sorted */
    }while(pEnd != pHead->next);
    return pHead;
}

Answer 2

First: bubblesort is terrible. For linked lists, it is even more terrible... [the "natural" way to sort a linked list is merge-sort, because zip-merging two sorted linked lists is easy]

For bubble sort,the elementary operation is:

• { compare two adjacent nodes, and MAYBE swap them }
• and repeat this until nothing changes.
• which implies that the final pass always does nothing.

---

#include <stdio.h>

struct node{
        struct node *next;
        int value;
        };

struct node nodes[] =
{{ nodes+1, 9}
,{ nodes+2, 5}
,{ nodes+3, 0}
,{ nodes+4, 1}
,{ nodes+5, 4}
,{ nodes+6, 7}
,{ nodes+7, 2}
,{ nodes+8, 3}
,{ nodes+9, 8}
,{ NULL   , 6}
        };

void node_printlist(struct node *p) {
for (   ;p; p=p->next) {
        printf("%d\n", p->value);
        }
}

unsigned node_bubblepass(struct node **pp)
{
struct node *one, *two;
unsigned swaps;

for (swaps=0 ; one = *pp; pp=&(*pp)->next) {
        two = one->next;
        if(!two) break;
        if(two->value >= one->value) continue;
                /* wrong order: swap them*/
        one->next = two->next;
        two->next = one;
        *pp = two;
        swaps++;
        }
return swaps;
}

void node_bubblesort(struct node **pp)
{
unsigned swaps;
do      {
        swaps = node_bubblepass(pp);
        } while (swaps);
}

int main(void){
struct node *root =nodes;

printf("Original:\n");
node_printlist(root);

node_bubblesort(&root);

printf("Result:\n");
node_printlist(root);

return 0;
}

---

UPDATE (thanks to @rcgldr) in the innerloop we can stop to bubble down when we hit an item that has been bubbled down before.

struct node * node_bubblepass_2(struct node **pp, struct node *end)
{
struct node *one, *two;

for ( ; one = *pp; pp=&(*pp)->next) {
        two = one->next;
        if(two == end) break;
        if(two->value >= one->value) continue;
                /* wrong order: swap them*/
        one->next = two->next;
        two->next = one;
        *pp = two;
        }
return one;
}

void node_bubblesort_2(struct node **pp)
{
 struct node *end = NULL;
do      {
        end = node_bubblepass_2(pp, end);
        } while (*pp != end);
}