Change address of pointer to linked list when sorting

Question

This is my program to sort a linked list by Bubble sort. When I use while it is OK, but when I use for loop it have an infinite loop so my program is stop unexpectedly. On the other hand, for the first swap of first and second element, I change pointer head point to the second but maybe it doesn't work for the whole program.

For example, Ex1: Input : 3,2,4,1,5 Output: 2,3,4,5

Ex2: Input: 4,3,2,1,5 Output:3,4,5

Ex3: Input: 3,2,1 Output: 2,3

I think that it just change the address the head pointer point to for the first time, so head is point to 2 in Ex1, 3 in Ex2 and 2 in Ex3.

void Swap(Node *p1, Node *p2)
{
    Node *t;
    t=p2->next;
    p2->next=p1;
    p1->next=t;
}


Node *BubbleSort(Node *head,int n) //pass the address of the first element in linked list and the linked list size 
{
    Node *tmp=head;
    int swap=1;

    for(int i=0;i<n-1;i++)
    {
        tmp=a; swap=0;
       for(int j=0;j<n-1;j++)
       {
         if((tmp->data)>(tmp->next->data))
         {
             if(j==0)  //if this is the first and second element I will change the address of the pointer
                a=tmp->next;

             Swap(tmp,tmp->next);   
             swap=1;
         }
         else tmp=tmp->next; //If the element I focus on is not greater than its folowing I will move the tmp pointer to the next.
        }       
        
        if(swap==0)
           return head;
    }
    return head;
}

int main()
{
    Node*head;
   //Assume I have a linked list with n elements
    head=BubbleSort(head,n);
   
}

I searched for an other way in GeekforGeek but I still want to know why my code doesn't work. I have think for almost a long day. Please help me !

Answer 1

The Swap function is off by one. Therefore, in the innermost loop body you need to Swap(tmp->prev, tmp) instead of Swap(tmp, tmp->next).

You need to compare and swap the same elements, not compare the current and next element but swap the next and 2nd next element. if( (tmp->data) > (tmp->next->data) ), then tmp->prev->next should point to tmp->next and tmp->next->next should point to tmp. However, there is one thing to take care of: As you Swap(tmp->prev, tmp) you need to start one element further, too. This is also clear from the fact that the head points to the first element but does not contain any data. first->prev should point to the head, the head should be rw.

It's possible to let the top level code maintain the head but it's better if the ll code maintains it's own head.