CODEWITHSUNDEEP
csortinglinked-listbubble-sort
Naufil Muhammad
Naufil Muhammad

Reputation: 59

Unable to sort linked list in ascending order in C

I am trying to make Library Management System program on C using Code Block editor.

So far I have been successful in making the program print list of library books with their names and author's name, but when it asks if I want to arrange it in ascending order and I press 'y', it again prints the same list without arranging it in ascending order (I am trying to sort using Bubble Sort Algorithm).

Please modify the code accordingly with detailed explanation.

Original:

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

struct Node {
    char name[50];
    char author[50];
    struct Node* next;
};
struct Node* head; // Global Variable
void Insert(char q[50], char r[50]);
void Print();
void bsort();

int main()
{
    int n,i; //Local Variables
    char x[50],y[50]; // Local Variables
    char d;
    head=NULL; //Initially head is null
    printf("How many books you want to enter?: ");
    scanf("%d",&n);
    for (i=1; i<=n; i++) // Loop iterate the number of times we have books in quantity.
    {
        printf("Enter a Book name: ");
        fflush(stdin); // To clear buffer memory
        gets(x); // Same as scanf
        printf("Author: ");
        gets(y);
        Insert(x,y);

    }
    Print();
    printf("Do you want to sort the data in ascending order?(y/n): ");
    scanf("%c",&d);
    printf("Your pressed %c",d);
    if (d=='y')
    {
        bsort();
        Print();
    }
    else
        printf("alright!");

    return 0;
}

void Insert(char q[50], char r[50]) //Adding items at the end of linked list
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next=NULL; // Since we are adding a node to the end, we are linking it to NULL.
    strcpy(temp->name,q); // copying the contents of "q" to "temp->name"
    strcpy(temp->author,r); // same
    if(head==NULL)
    {
        head=temp;
    }
    else
    {
        struct Node* temp1 = head;
        while(temp1->next!=NULL)
            temp1=temp1->next;
        temp1->next=temp;
    }
}
void Print() //Traversing
{
    printf("\n");
    printf("The Library data is as follows: \n");
    struct Node* temp=head;
    printf("\n");
    while(temp!=NULL)
    {
        printf("%25s",temp->name);
        printf("%25s",temp->author);
        temp=temp->next;
        printf("\n");
    }
}

void bsort() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }
    {
        for (k=1; k=count-1; k++)
        {
            for (i=head; i<=NULL-k; i=i->next)
            {
                if(i->name>j->name)
                {
                    strcpy(temp3,i->name);
                    strcpy(i->name,j->name);
                    strcpy(j->name,temp3);
                }
                j=j->next;
            }
        }
    }
}

First Edit: 

void bsort() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }

    for (k=1; k=count-1; k++)
    {
        for (i=head; i<=count-k; i=i->next)
        {
            if (strcmp(i->name,j->name)>0)
            {
                strcpy(temp3,i->name);
                strcpy(i->name,j->name);
                strcpy(j->name,temp3);
            }
            j=j->next;
        }
    }
}

Second edit:

void bsort() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }

    for (k=1; k<=count-1; k++)
    {
        for (i=head; i<=count-k; i=i->next)
        {
            if (strcmp(i->name,j->name)>0)
            {
                strcpy(temp3,i->name);
                strcpy(i->name,j->name);
                strcpy(j->name,temp3);
            }
            j=j->next;
        }
    }
}

Third Edit

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

struct Node {
    char name[50];
    char author[50];
    struct Node* next;
};
struct Node* head; // Global Variable
void Insert(char q[50], char r[50]);
void Print();
void bsort_print();
int main()
{   int n,i; //Local Variables
    char x[50],y[50]; // Local Variables
    char d;
    head=NULL; //Initially head is null
    printf("How many books you want to enter?: ");
    scanf("%d",&n);
    for (i=1; i<=n; i++) // Loop iterate the number of times we have books in quantity.
    {
        printf("Enter a Book name: ");
        fflush(stdin); // To clear buffer memory
        gets(x); // Same as scanf
        printf("Author: ");
        gets(y);
        Insert(x,y);

    }
    Print();
    printf("Do you want to sort the data in ascending order?(y/n): ");
    scanf("%c",&d);
    printf("Your pressed %c",d);
    if (d=='y')
    {
        bsort_print();
    }
    else
        printf("alright!");

    return 0;
}

void Insert(char q[50], char r[50]) //Adding items at the end of linked list
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next=NULL; // Since we are adding a node to the end, we are linking it to NULL.
    strcpy(temp->name,q); // copying the contents of "q" to "temp->name"
    strcpy(temp->author,r); // same
    if(head==NULL)
    {
        head=temp;
    }
    else {
        struct Node* temp1 = head;
        while(temp1->next!=NULL)
            temp1=temp1->next;
        temp1->next=temp;
    }
}
void Print() //Traversing
{
    printf("\n");
    printf("The Library data is as follows: \n");
    struct Node* temp=head;
    printf("\n");
    while(temp!=NULL)
    {
        printf("%25s",temp->name);
        printf("%25s",temp->author);
        temp=temp->next;
        printf("\n");
    }
}
void bsort_print() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    struct Node* current=i;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }

    for (k=1; k<=count-1; k++)
    {
        for (count=1; count<count-k; count++)
        {
            if (strcmp(i->name,j->name)>0)
            {
                strcpy(temp3,i->name);
                strcpy(i->name,j->name);
                strcpy(j->name,temp3);
            }
            j=j->next;
        }
    }
    printf("\n");
    printf("The Library data is as follows: \n");
    printf("\n");
    while(current!=NULL)
    {
        printf("%25s",current->name);
        printf("%25s",current->author);
        current=current->next;
        printf("\n");
    }
}

Upvotes: 0

Views: 851

Answers (1)

Tommaso Fontana
Tommaso Fontana

Reputation: 730

Problems with your implementation of Bubble Sort

Your implementation of Bubble Sort has a few problems:

  1. I think that you mean i <= count-k instead of i<=NULL-k because NULL == 0 so the statement i<=NULL-k is equivalent to i<=-k and to i > k.

  2. Use strcmp instead of i->name>j->name because you are comparing the address of the arrays not the names.

  3. You forgot to swap the authors in your struct.

A better implementation

What needed changing in the rest of the code

  1. Instead of repeating 50 every time you have an array use #define MAX_STRING_LENGTH 50 which is more readable and if you need to change it you can do it without having to search every occurence in the code.

  2. void Insert(char q[50], char r[50]); you don't need to specify the dimension of the arrays in the parameters of the functions, you can just void Insert(char *p, char *r); which refers to generic pointer to char.

  3. Instead of saving the user input in two arrays and then copy them to the array in the node it's more efficent to just allocate using the malloc function the new arrays and then just coping the reference to it into the node. This allows you to not use the strcpy which is an O(n) and slow down a lot the code.

  4. Define a new variable type with typedef struct node {<ARGS>} Node; so you can write Node* instead of struct Node* which is more readable.

Ciclomatic Complexity

This are the results of the analysis of the CC of the Bubble Sort with the site lizard.ws:

your code complexity

the new code complexity

// Imports
//---------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//---------------------------------------------
// Definitions
//---------------------------------------------
#define MAX_STRING_LENGTH 50
//---------------------------------------------
// Type definitions to make the code more readable
//---------------------------------------------
typedef struct node {
    char *name;
    char *author;
    struct node * next;
} Node;
//---------------------------------------------
// Global Variable
//---------------------------------------------
Node* head = NULL;
//---------------------------------------------
// Function protoypes
//---------------------------------------------
void insert(char *q, char *r);
void print_the_list();
void bsort();
//---------------------------------------------
// Main Function :
// Ask the user to insert some books then
// print the list of books
// normally or sorted by book name
//---------------------------------------------
int main() {
    head = NULL; //Initially head is null

    char *book_name, *book_author;

    int n; // Number of book that the user want to enter
    printf("How many books you want to enter?: \n");
    scanf("%d", &n);

    for (int i = 1; i <= n; i++){ // Loop iterate the number of times we have books in quantity.
        // To clear buffer memory
        fflush(stdin);

        // get the name
        printf("Enter a Book name: \n");
        // allocate the memory for the name of the new book
        book_name = (char*) malloc(MAX_STRING_LENGTH*sizeof(char));
        gets(book_name); // Same as scanf

        // get the author
        printf("Author: \n ");
        // allocate the memory for the author of the new book
        book_author = (char*) malloc(MAX_STRING_LENGTH*sizeof(char));
        gets(book_author);

        // add it to the list
        insert(book_name, book_author);

    }

    print_the_list();
    char d;
    printf("Do you want to sort the data in ascending order?(y/n): \n\t");
    scanf("%c", & d);
    if (d == 'y') {
        printf("Soprting the list!");
        bsort();
    } else
        printf("alright!");

    print_the_list();
    return 0;
}
//---------------------------------------------
// insert(name of the book, authro of the book):
// O(n_of_element_in_the_list)
// append the new book the global list
//---------------------------------------------
void insert(char* name, char* author){ //Adding items at the end of linked list
    // create and initialize the new node
    Node* new_node = (Node* ) malloc(sizeof(Node));
    new_node->author = author;
    new_node->name   = name;
    new_node->next   = NULL; // Since we are adding a node to the end, we are linking it to NULL.

    // if the list is empty then add the node as the head of the list
    if (head == NULL) {
        head = new_node;
    }
    else {
        Node * temp = head;
        // Traverse the list till the end
        while (temp->next != NULL)
            temp = temp->next;
        // add the new node as the successor of the last node
        temp->next = new_node;
    }
}

//---------------------------------------------
// print_the_list():
// O(n_of_element_in_the_list)
// print the whole content of the global list
//---------------------------------------------
void print_the_list(){
    printf("\nThe Library data is as follows: \n\n");
    Node* temp = head;
    while (temp != NULL) {
        printf("%s\n%s\n\n", temp->name,temp->author);
        temp = temp->next;
    }
}

//---------------------------------------------
// sort():
// O(n_of_element_in_the_list^2)
// sort the whole list by name in Ascending Order
//---------------------------------------------
void bsort(){ //Bubble Sort Algorithm to arrange Library data in Ascending Order
    char *swap_ptr_name, *swap_ptr_author;
    // for each node of the list
    for (Node* current_minimum = head; current_minimum != NULL; current_minimum = current_minimum->next) {
        // for each node after the current_minimum
        for (Node* current_node = current_minimum->next; current_node != NULL;  current_node = current_node->next) {
            // if the current_node is less than the current_minimum swap them
            if (strcmp(current_node->name,current_minimum->name) < 0) {
                // Save the name and author of the current_minimum
                swap_ptr_name   = current_minimum->name;
                swap_ptr_author = current_minimum->author;

                // Place the current node as the minimum
                current_minimum->name   = current_node->name;
                current_minimum->author = current_node->author;

                // Place the old minimum in the place of the current_node
                current_node->name   = swap_ptr_name;
                current_node->author = swap_ptr_author;
            }
        }
    }
}

Additional Notes

Code Formatting

I suggest you to read some code style guides (GNU,Google) because in C if you aren't really precise the code becomes unreadable very fast.

To start I think the best is to get used to use:

  1. #define for definitions

  2. typedef to define new variable type so you don't have to wirte the struct every time

  3. comment A LOT the code.

Edit

I apologize, The algorithm I implemented was not the Bubble Sort.

The actual Bubble Sort implementation is this:

//---------------------------------------------
// sort():
// O(n_of_element_in_the_list^2)
// sort the whole list by name in Ascending Order
//---------------------------------------------
void bsort(){ //Bubble Sort Algorithm to arrange Library data in Ascending Order

    // If he list is empty then is already sorted
    if(head == NULL)
        return;

    // Temp pointers to swap two nodes.
    char *swap_ptr_name, *swap_ptr_author;
    // Variable that keep track if at least one swap was made in the for.
    int swapped;


    Node* next_node;
    do{
        // Reset the flag
        swapped = 0;
        // for each node in the list except the last one
        for (Node* current_node = head; current_node->next != NULL;  current_node = current_node->next) {
            // Set the next node 
            next_node = current_node->next;
            // if the current_node is bigger than the next_node swap them
            if (strcmp(current_node->name,next_node->name) > 0) {
                // Save the name and author of the current_minimum
                swap_ptr_name   = next_node->name;
                swap_ptr_author = next_node->author;

                // Place the current node as the minimum
                next_node->name   = current_node->name;
                next_node->author = current_node->author;

                // Place the old minimum in the place of the current_node
                current_node->name   = swap_ptr_name;
                current_node->author = swap_ptr_author;

                // We swapped two nodes so the flag is setted
                swapped = 1;
            }
        }
    }while(swapped == 1);
}

Additional Notes Pt.2

There is a way to swap variables without having the swap ptr but it's less readable. The XOR Swap

In this case it would look like this.

// X := X XOR Y
current_node->name   ^= next_node->name;
current_node->author ^= next_node->author;

// Y := Y XOR X
next_node->name   ^= current_node->name;
next_node->author ^= current_node->author;

// X := X XOR Y
current_node->name   ^= next_node->name;
current_node->author ^= next_node->author;

Upvotes: 4

Related Questions