Sorting a single linked list algorithm in C does not work(Bubblesort with swapping the Nodes, not th-CodePudding

currently i'm trying out some algorithms. The Bubblesort with swapping the data works fine, but when i try to use the swap adress function the program ends with an error. I hope someone can help me The structure i use is:

struct Node_s{
int data;
struct Node_s *next;
};
typedef struct Node_s Node_t;

Thats my function to swap the nodes:

Node_t* swap_adr(Node_t *ptr1, Node_t *ptr2)
{
    Node_t *temp;
    temp=ptr2->next;
    ptr2->next=ptr1;
    ptr1->next=temp;
    return ptr2;

}

Thats the function which calculates the length of the list:

int len(Node_t* head)
{
    Node_t* temp = head ;
    int i = 0 ;
    while(temp!=NULL)
    {
        i  ;
        temp=temp->next ;
    }

    return i ;
}

Thats the BubbleSort funciton which does not work:

void bubbleSort(Node_t* head)
{
    int length=len(head);
    Node_t* temp;
    int i, j, swapped;
    Node_t* p1,*p2;


    for(i=0;i<=length;i  )
    {
        temp = head;
        swapped = 0;

        for (j = 0; j < length  - 1; j  )
        {

            p1 = temp;
            p2 = p1->next;

            if (p1->data > p2->data)
            {

                /* update the link after swapping */
                temp = swap_adr(p1, p2);
                swapped = 1;
            }
            temp = temp->next;
        }
    }
}

The strange thing is, this code works, i don't understand why?

void bubbleSort(Node** head)
{
    int length=len(*head);
    Node** temp;
    int i, j, swapped;
    Node* p1,p2;
  
    for (i = 0; i <= length; i  )
    {
  
        temp = head;
        swapped = 0;
  
        for (j = 0; j < length - i - 1; j  ) 
        {
  
            p1 = *temp;
            p2 = p1->next;
  
            if (p1->data > p2->data)
            {
  
                /* update the link after swapping */
                *temp = swap(p1, p2);
                swapped = 1;
            }
  
            temp = &(*temp)->next;
        }

        if (swapped == 0)
            break;
    }
    return;
}

CodePudding user response：

You need an extra variable for the previous node (i.e. the one before p1).

When you swap the next pointers in the loop, you have to change prev->next from p1 to p2

Here is some refactored code. It is annotated. I've compiled it but not tested it:

#include <stdio.h>

typedef struct node {
    int data;
    struct node *next;
} Node_t;

void
bubbleSort(Node_t *head)
{
    Node_t *temp;
    Node_t *rhs;
    Node_t *lhs;
    Node_t *prev;

    // get list total length
    int length = 0;

    for (temp = head; temp != NULL; temp = temp->next)
          length;

    // reduce length by one on each pass (the last element on each pass is
    // correct -- no need to rescan)
    for (; length > 1; --length) {
        int swapped = 0;

        // get the two pointers
        rhs = NULL;
        lhs = head;
        if (lhs != NULL)
            rhs = lhs->next;

        prev = NULL;
        int i = 1;

        for (; rhs != NULL; prev = lhs, lhs = rhs, rhs = rhs->next,   i) {
            // no need to traverse the entire list on subsequent passes
            if (i >= length)
                break;

            // nodes are in sort
            if (lhs->data <= rhs->data)
                continue;

            // swap the node pointers
            temp = lhs->next;
            lhs->next = rhs->next;
            rhs->next = temp;

            // link previous node to new lhs (i.e. rhs)
            if (prev != NULL)
                prev->next = rhs;

            // new list head
            else
                head = rhs;

            // swap lhs/rhs so that the for loop works
            temp = lhs;
            lhs = rhs;
            rhs = temp;

            // say a swap was done
            swapped = 1;
        }

        // early escape if no swap
        if (! swapped)
            break;
    }
}

CodePudding user response：

If you want to swap addresses, then you have to pass the addresses of the two elements you want to swap.

For example, if you want to swap pointers, which are basically addresses, then you have to pass the addresses of the addresses. Thus:

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

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

void node_swap(struct node **p, struct node **q) // Pass the address of (struct node*)
{
    struct node *tmp = *p;
    *p = *q;
    *q = tmp;
}

int main(void)
{
    struct node *n1 = malloc(sizeof *n1);
    struct node *n2 = malloc(sizeof *n2);
    
    n1->data = 1;
    n2->data = 2;
    
    printf("N1 = %d\n", n1->data);
    printf("N2 = %d\n", n2->data);
    
    node_swap(n1, n2);
    
    printf("N1 = %d\n", n1->data);
    printf("N2 = %d\n", n2->data);
    
    free(n1);
    free(n2);
}

Output:

N1 = 1
N2 = 2
N1 = 2
N2 = 1

EDIT You probably should avoid typedefing your structs. But in case you insist on that, here's how your code should look like:

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

typedef struct node  node_s;
typedef struct node *node_ptr;

void node_swap(node_ptr *p, node_ptr *q) // Pass the address of p and q
{
    node_ptr tmp = *p;
    *p = *q;
    *q = tmp;
}