Bubble Sort on Linked List Shortening List-CodePudding

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

Node* initNode(){
  Node* newN = malloc(sizeof(Node));
  newN->data = rand() % (1000 -0);
  newN->next = NULL;
}

void addNodes(int amount, Node* first){
  Node* cur = first;
  while(cur->next != NULL){
    cur = cur->next;
  }
  for(int i = 0; i <= amount; i  ){
    cur->next = initNode();
    cur = cur->next;
  }
}

void printNodes(Node* first){
  Node* cur = first;
  int loopC = 0;
  while(cur->next != NULL){
    printf("%d-", cur->data);
    loopC  ;
    cur = cur->next;
  }
}

beginning of areas causing problem I think that it is something wrong with the sort or swap functions causing the shortening of the linked list, not sure though.


void swap(Node* prev, Node* cur, Node* first){
  Node* next = cur->next;
  if(next==NULL){return;}
  Node* nextO = next->next;
  cur->next = nextO;
  if(prev != NULL){prev->next = next;}
  else{first = next;}
  next->next = cur;

}

void bubbleSort(Node* first){
  int switchC = -1;
  while(switchC != 0){
    switchC = 0;
    Node* cur = first;
    Node* prev = NULL;
    Node* next = NULL;
    while(cur->next != NULL){
      next = cur->next;
      if(next->data <= cur->data){
        swap(prev, cur, first);
        switchC  ;
      }
      prev = cur;
      cur = next;      
    }
  }
}

end of areas causing problem


void main(){
  Node* first = initNode();
  addNodes(10, first);
  printNodes(first);
  bubbleSort(first);
  printNodes(first);
}

inputed linked list: Node 0: value:383-Node 1: value:886-Node 2: value:777-Node 3: value:915-Node 4: value:793-Node 5: value:335-Node 6: value:386-Node 7: value:492-Node 8: value:649-Node 9: value:421-Node 10: value:362

Outputed Linked List: Node 0: value:383-Node 1: value:386-Node 2: value:421-Node 3: value:492-Node 4: value:649-Node 5: value:777-Node 6: value:793-Node 7: value:886

CodePudding user response：

I don't see why you need a prev pointer in your bubbleSort function. Also, you don't have to change pointers in your swap function. Since the size of the list won't change, you can merely swap the data field.

Be careful no to squeeze your code this much. It's hard to follow. Start with a known data (such as the vector 100,99,...,89 below). Will be much easier to debug.

Here's a possible fix with minimum changes to your code:

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

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

int count = 100;

Node* initNode(){
  Node* newN = malloc(sizeof(Node));
  newN->data = count--;
  newN->next = NULL;
}

void addNodes(int amount, Node* first){
  Node* cur = first;
  while(cur->next != NULL){
    cur = cur->next;
  }
  for(int i = 0; i <= amount; i  ){
    cur->next = initNode();
    cur = cur->next;
  }
}

void printNodes(Node* first){
  Node* cur = first;
  int loopC = 0;
  while(cur != NULL){
    printf("%d-", cur->data);
    loopC  ;
    cur = cur->next;
  }
  printf("\n");
}

void swap(Node* node1, Node* node2)
{
  int tmp = node2->data;

  node2->data = node1->data;
  node1->data = tmp;
}

void bubbleSort(Node* first)
{
  int switchC = -1;

  while(switchC != 0) {

    switchC = 0;
    Node* cur = first;
    Node* next = NULL;

    while ((next = cur->next) != NULL) {

      if(next->data <= cur->data) {

        swap(cur, next);

        switchC  ;
      }

      cur = next;
    }
  }
}

void main()
{
  Node* first = initNode();

  addNodes(10, first);

  printNodes(first);

  bubbleSort(first);

  printNodes(first);
}

Output:

$ gcc main.c && ./a.out
100-99-98-97-96-95-94-93-92-91-90-89-
89-90-91-92-93-94-95-96-97-98-99-100-

CodePudding user response：

You claim that the problem is in your Bubblesort implementation, but there is at least a problem in printNodes():

void printNodes(Node* first){
  Node* cur = first;
  int loopC = 0;
  while(cur->next != NULL){
    printf("%d-", cur->data);
    loopC  ;
    cur = cur->next;
  }
}

Observe that the last node in the list will not satisfy the condition cur->next != NULL, and therefore its value will not be printed. It is worth also mentioning at this point that the representations of the input and output linked lists presented in the OP were not produced by the version of printNodes() presented there, which begs the question of where they did come from.

It turns out that you are right about there being a bug in your sort, however. Both your swap() and your bubbleSort() are flawed. They accept the head pointer by value and return nothing, so when one of these functions tries to assign a different node to be the head node, that change does not propagate to the function's caller.

There are two possible solutions for that in the bubbleSort() function:

Pass a pointer to the head pointer:
```
void bubbleSort(Node **first) // ...
```
Erstwhile uses of first would need to be adjusted to *first.
Return the new value of first, making it the caller's responsibility to update its head-node pointer.
```
Node *bubbleSort(Node *first) {
    // ...
    return first;
}
```

The same applies to your swap() function, but there you have an additional option: restructure bubbleSort so that the prev argument to swap() is never null. You can do this by temporarily inserting a dummy head node in front of the true head, and structuring the sort passes so that the dummy is never evaluated for exchange with its successor. This permits you to make the head node an ordinary case instead of a special one. I leave the details to you to work out if you wish, but here's a start:

void bubbleSort(Node **first) {
    Node dummy = { .next = *first };

    // ...

    *first = dummy.next;
}

If you pursue this then you should find that swap() does not need the third argument, as its prev will always be non-NULL (sometimes it may be &dummy). The simplification may even be enough that you decide you don't need a separate swap() function in the first place.