The last node in linked list not working in Bubble sort-CodePudding

i try to sort a linked list using bubble sort algorithm, but the last node seems to not sorted in the list. Every element in the list can be sorted but except the last one. Can anyone suggest me where i'm doing wrong and how to fix it? Thanks a lot! ( Sorry for bad English ), Here is my code:

struct Node{
    int data;
    Node *next;
};

bool isEmpty(Node *head){
    if (head == NULL){
        return true;
    }
    else{
        return false;
    }
}

void insertAsFirstElement(Node *&head, Node *&last, int number){
    Node *temp = new Node;
    temp -> data = number;
    temp -> next = NULL;
    head = temp;
    last = temp;
}


void insert(Node *&head, Node *&last, int number){
    if (isEmpty(head)){
        insertAsFirstElement(head , last , number);
    }
    else{
        Node *temp = new Node;
        temp->data = number;
        temp->next = NULL;
        last->next = temp;
        last = temp;
    }
}

void BubleSort(Node *&head){
    struct Node *i ,*j;
    int num;
    for (i = head; i-> next != NULL;i=i->next){
        for (j = i->next; j->next != NULL; j = j->next){
            if (i->data > j-> data){
                num = j->data;
                j->data = i->data;
                i->data = num;
            }
        }
    }
    
}


void display(Node *current){
    if (current == NULL){
        cout<<"Nothing to display ";
    }
    while(current!= NULL){
        cout<<current -> data<<"-> ";
        current = current -> next;
    }
}

int main(){
    Node *head = NULL;
    Node *last = NULL;
    int T;cin>>T;
    for (int i=0 ;i<T;i  ){
        int number;cin>>number;
        insert(head,last,number);
    }
    BubleSort(head);
    display(head);
}

Input:

6
1 7 4 6 9 3

Output:

1-> 4-> 6-> 7-> 9-> 3->

CodePudding user response：

first of all, j->next will be 0 if j is the last element in the list. so j will skip the last element.

second of all, if you let j iterate from i to the end of the list and increase i every time, you'll skip elements. you need to move the end point to the left (aka decrease the end index) instead of moving the start to the right (aka increasing the start index).

edit: to get what i mean you might wanna check this out

this is hard to do, because your list is built up with pointers pointing to the next element, not reverse. but is definitely managable by stopping j before reaching the end (unfixing the 1st point) and replacing i with j.

    void BubleSort(Node*& head) {
    struct Node* i, * j;

    //move i to the end
    for (i = head; i->next != NULL; i = i->next)
    {
    }

    do {
        //loop from the start to i
        for (j = head; ; j = j->next) {
            //compare the element 'at index' j with the next element ('j   1')
            if (j->data > j->next->data) {
                //nice simple function to do swapping, provided by the std library.
                std::swap(j->data, j->next->data);
            }
            if (j->next == i)
            {
                //move i one to the 'left' aka decrease by it by one aka move it up one step in the recursion
                i = j;
                break;
            }
        }
    } while (i != head);
}