Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

Hello,

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

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();
}
```

Linear singly linked list

Circular singly linked list

Two way or doubly linked list

Circular doubly linked list.

After performing the sort, you need to set temp as the new start node of the linked 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

>> 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);
}
```

'node' is local to the function. Any change to it will not be visible outside of the function.

You'll need to somehow set the pointer to the first node of the linked list to point to the same node as 'temp'.

>>>>then call it like this:

> ...

> item* root = new item;

> ...

> root = bubble_sort( root );

> ...

> ...

> item* root = new item;

> ...

> root = bubble_sort( root );

> ...

> ...

> 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.c

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:

> void bubble_sort( item* );

> // ... any code

> item* bubble_sort( item* node )

> {

> ...

> }

So the declaration and the implementation use different return types.

Sorry, I forgot to change the function prototype on top of the program...

But, still not working.

I am now getting the "Unhandled exception at 0x00411c6e in LinkedListExercice.exe: 0xC0000005: Access violation reading location 0xcdcdcdd1." error...

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.

```
#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);
}
```

>> 32 item* root = new item;

And :

>> 72 PrintList(root);

needs to be :

PrintList(head);

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.

Question has a verified solution.

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

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

Make that :

head = bubble_sort(head);

because head is the global pointer that points to the start of the linked list.

>> 304 return first_prev;

Make that :

return temp;

because that's the pointer that points to the beginning of the sorted list.