Solved

Bubble Sorting a Linked List in C

Posted on 2010-08-20
21
671 Views
Last Modified: 2012-08-13
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
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();
}

Open in new window

0
Comment
Question by:Smanyx
  • 8
  • 8
  • 2
  • +2
21 Comments
 
LVL 3

Expert Comment

by:shaleesh
ID: 33484255
What is the type of Linked list you are using?

Linear singly linked list
Circular singly linked list
Two way or doubly linked list
Circular doubly linked list.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33484641
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 33484696
How does  PrintList() know where to start?

\
0
Windows Server 2016: All you need to know

Learn about Hyper-V features that increase functionality and usability of Microsoft Windows Server 2016. Also, throughout this eBook, you’ll find some basic PowerShell examples that will help you leverage the scripts in your environments!

 
LVL 31

Expert Comment

by:Zoppo
ID: 33485100
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
 

Author Comment

by:Smanyx
ID: 33485241
>> '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);
} 

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33485281
>> node = temp;

'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'.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33485287
Could you show how you call the bubble_sort function ? (or better yet : could you post the complete code here)
0
 
LVL 84

Expert Comment

by:ozo
ID: 33485295
How do you find the start of the list to see?
0
 

Author Comment

by:Smanyx
ID: 33485375
>>>>then call it like this:
> ...
> item* root = new item;
> ...
> root = bubble_sort( root );
> ...
0
 

Author Comment

by:Smanyx
ID: 33485429
>>>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 *)'
 
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33485435
Could you post the complete code here ? That'll make things a lot easier ...
0
 
LVL 31

Expert Comment

by:Zoppo
ID: 33485486
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:

> void bubble_sort( item* );
> // ... any code
> item* bubble_sort( item* node )
> {
>  ...
> }

So the declaration and the implementation use different return types.
0
 

Author Comment

by:Smanyx
ID: 33485561
>> error C2556: 'item *bubble_sort(item *)' : overloaded function differs only by return type from 'void bubble_sort(item *)'

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...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33485625
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
 

Author Comment

by:Smanyx
ID: 33485779
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", &current->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);
}

Open in new window

0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 250 total points
ID: 33485848
>> 70                         root = bubble_sort( root );

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.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33485868
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
 

Author Closing Comment

by:Smanyx
ID: 33486079
Thank you very much. It's working fine now. That's a relief !!
0
 

Author Comment

by:Smanyx
ID: 33486264
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.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 33486305
>> 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
 

Author Comment

by:Smanyx
ID: 33486341
Okay. Thanks heaps.
0

Featured Post

Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

815 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now