I am having trouble with this function to bubble sort a linked list. I am losing nodes. Could you please help me understand what I am doing wrong and get this right?

Thanks

void bubble_sort(item *node){ item *first_prev,*first,*second,*temp; int i, j, n = 1; bool sorted = false; //make these 3 pointers point to the head of the list temp = node; first = node; first_prev = node; //count the number of nodes in the list while (first->next != NULL) { n++; first= first->next; } for (i = 1; i <= n; i++) { first = temp; first_prev = temp; second = first->next; for (j=1; j<=(n-i); j++) { if (first->val > second->val) { if (first == temp) { first->next = second->next; second->next = first; temp = second; first = second; } else { first->next = second->next; second->next = first; first_prev->next = second; first = second; } } first_prev = first; first = first->next; second = first->next; } } sorted = true; PrintList();}

I don't see a problem with your bubble sort algorithm. However, keep in mind that after the sorting, 'temp' points to the first node in the sorted list. 'node' might no longer point to the start of the sorted linked list, but will very likely point to another node in the sorted linked list.

After performing the sort, you need to set temp as the new start node of the linked list.

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

Infinity08 and ozo are right - the sort-function needs to return the pointer to the first element in the sorted list.

To do so implement the sort function like this:

> item* bubble_sort(item *node)
> {
> ... // your code
> return first_prev; // return head item
> }

then call it like this:
> ...
> item* root = new item;
> ...
> root = bubble_sort( root );
> ...

Hope that helps,

ZOPPO

0

SmanyxAuthor Commented:

>> 'temp' points to the first node in the sorted list
>> you need to set temp as the new start node of the linked list.

Outside of the loop, after the sorting is over, I set :
node = temp;
first = node;

But still not working. I can't see all nodes sorted.

void bubble_sort(item *node){ item *first_prev,*first,*second,*temp; int i, j, n = 1; bool sorted = false; //make these 3 pointers point to the head of the list temp = node; first = node; first_prev = node; //count the number of nodes in the list while (first->next != NULL) { n++; first= first->next; } for (i = 1; i <= n; i++) { first = temp; first_prev = temp; second = first->next; for (j=1; j<=(n-i); j++) { if (first->val > second->val) { if (first == temp) { first->next = second->next; second->next = first; temp = second; first = second; } else { first->next = second->next; second->next = first; first_prev->next = second; first = second; } } first_prev = first; first = first->next; second = first->next; } } sorted = true; node = temp; first = node; //PrintList(node);}

>>>>then call it like this:
> ...
> item* root = new item;
> ...
> root = bubble_sort( root );
> ...

0

SmanyxAuthor Commented:

>>>then call it like this:
> ...
> item* root = new item;
> ...
> root = bubble_sort( root );
> ...

Isn't this more C++ synthax? With the "new" keyword.
It's not working.
I am getting the following error:
\linkedlistexercice\main.cpp(342) : error C2556: 'item *bubble_sort(item *)' : overloaded function differs only by return type from 'void bubble_sort(item *)'

ah, yes, it's C++ - but since you have a 'cpp' file I guess you do C++ and then 'new' is the recommended way to allocate memory.

About the error: I guess you somewhere have a function prototype declaration (maybe in a header or in 'main.cpp') for 'bubble_sort'm somehow like this:

We can't guess what your code looks like, so any suggestions we make will likely not work.

As I asked before, could you please post the complete code here. That way, we can make the correct suggestion right away, and immediately solve your problem.

0

SmanyxAuthor Commented:

Here is the full code as it stands now...

#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <string.h>// Structure definition (template)struct list_el{ int val; struct list_el *next;};typedef struct list_el item;item *head = NULL;void initialize(item*);void InsertItem();void DeleteItem();void PrintList(item* head);void FindItem();//void SortList(item *head, int count);//void bubble_sort(item *node);item* bubble_sort(item *node);//void sort(item *node);//void swap(item *first, item *first_prev,item *second,item *second_prev);void main(){ int choice; int count = 0; item* root = new item; do { printf("\n\tWELCOME TO ADVANCED PROGRAMMING\n"); printf("\n\tHere is a taste of working with Linked List in C\n\n"); printf("\n\t1. Insert an item \n"); printf("\n\t2. Delete a particular item\n"); printf("\n\t3. Print all the items\n"); printf("\n\t4. Find an item\n"); printf("\n\t5. Sort List\n"); printf("\n\t6. Quit \n"); printf("\n\n\tPlease enter your choice: "); scanf("%d",&choice); switch(choice) { case 1: system("cls"); InsertItem(); break; case 2: DeleteItem(); break; case 3: PrintList(head); break; case 4: FindItem(); break; case 5: //bubble_sort(head); //sort(head); root = bubble_sort( root ); PrintList(root); break; case 6: exit(1); break; } }while(choice != 6); printf("\n\tThanks for using this program.\n"); getch();}void initialize(item *current){ printf("\n\tEnter a number: "); scanf("%d", ¤t->val); current->next = NULL;}void InsertItem(){ item *newItem; newItem =(item*)malloc(sizeof(item)); initialize(newItem); if(head == NULL) { head = newItem; } else { item *current = head; // Move to the end of the linked list while(current->next != NULL) { current = current->next; } if(current->next == NULL) { newItem->next = current->next; current->next = newItem; } } //free(newItem);}void DeleteItem(){ item* current = head; int nodeNum; item *newItem,*temp; printf("\n\tEnter the item whose node you want deleted\n"); scanf("%d",&nodeNum); newItem = current; if(current->val == nodeNum) { // Deleting the first node newItem = current; current = current->next; free(newItem); head = current; return; } else { // Deleting an other node while(newItem->next->next != NULL) { if(newItem->next->val == nodeNum) { temp = newItem->next; newItem->next = newItem->next->next; free(temp); head = current; return; } newItem = newItem->next; } if(newItem->next->next == NULL && newItem->next->val == nodeNum) { // Check condition before deleting the last node free(newItem->next); newItem->next = NULL; head = current; return; } }}void PrintList(item* head){ item* current = head; printf("\n\t"); while(current!=NULL) { printf("%d -->",current->val); current = current->next; } printf("NULL");}void FindItem(){ int NumberToSearch, node = 1; bool Found = false; item * current = head; printf("\n\tEnter the value to search for in the list: "); scanf("%d", &NumberToSearch); while(current != NULL) { //if value is located in the first node if (current ->val == NumberToSearch ) { printf("\n\tValue %d found at node %d", NumberToSearch, node); Found = true; break; } else { current = current->next; node++; } } if (Found == false) { printf("\n\tValue %d not found.", NumberToSearch); }}//void SortList(item *head, int count)//{// //item * head;// int i, j/*, count*/;// item *p1, *p2, *p3;////// for(i = 1; i < count; i++)// {// p1 = head;// p2 = head->next;// p3 = p2->next;// // for(j = 1; j <= (count - i); j++)// {// if(p2->val < p3->val) // {// p2->next = p3->next;// p3->next = p2;// p1->next = p3;// p1 = p3;// p3 = p2->next;// }// else// {// p1 = p2;// p2 = p3;// p3 = p3->next;// // // }// }// }//void bubble_sort(item *node)item* bubble_sort(item *node){ item *first_prev,*first,*second,*temp; int i, j, n = 1; bool sorted = false; //make these 3 pointers point to the head of the list temp = node; first = node; first_prev = node; //count the number of nodes in the list while (first->next != NULL) { n++; first= first->next; } for (i = 1; i <= n; i++) { first = temp; first_prev = temp; second = first->next; for (j=1; j<=(n-i); j++) { if (first->val > second->val) { if (first == temp) { first->next = second->next; second->next = first; temp = second; first = second; } else { first->next = second->next; second->next = first; first_prev->next = second; first = second; } } first_prev = first; first = first->next; second = first->next; } } sorted = true; node = temp; first = node; return first_prev; //PrintList(node);}

Oh, and you probably want to remove this line again :

>> 32 item* root = new item;

And :

>> 72 PrintList(root);

needs to be :

PrintList(head);

0

SmanyxAuthor Commented:

Thank you very much. It's working fine now. That's a relief !!

0

SmanyxAuthor Commented:

Just a little worry that I have. I am using malloc() to allocate memory line 96:, I know I should free() the memory to eventually avoid memory leak. But how come I am getting a run-time error if I leave line 120: free(NewItem) in and nothing happens when I comment that out. It just runs ok.

>> But how come I am getting a run-time error if I leave line 120: free(NewItem) in and nothing happens when I comment that out. It just runs ok.

The memory you allocate is still used after the InsertItem function ends. You've placed the node in the linked list.

The free should be done when you remove the node from the linked list and when you destroy the entire linked list. So, it should be in your DeleteItem function, and at the end of main, you should empty the entire list.

0

SmanyxAuthor Commented:

Okay. Thanks heaps.

0

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Want an exciting career in an emerging field? Earn your MS in Cybersecurity and get certified in ethical hacking or computer forensic investigation. WGU’s MSCSIA degree program was designed to meet the most recent U.S. Department of Homeland Security (DHS) and NSA guidelines.

Linear singly linked list

Circular singly linked list

Two way or doubly linked list

Circular doubly linked list.