I am trying to sort a singly linked list using bubble sort. If there is a simple mistake then please pardon. Please tell me where I am going wrong. Program stops unexpectedly when I try to do this.
void sortBubble()
{
Node *i=start,*j=start;Node *temp;Node* prev=start;Node* agla;
while(i->next!=NULL)
{
cout<<"\nhello 1";
j=i;
agla=j->next;
while(agla!=NULL)
{
temp=NULL;temp->next=NULL;
cout<<"\nhello2";
if(*(j) > *(agla))
{
temp=agla->next;
agla->next=j;
prev->next=agla;
prev=agla;
agla=j->next;
j->next=temp;
}
else{
prev=j;
j=agla;
agla=j->next;}
}
prev=i;
i=i->next;
}
}
}
Your first obvious mistake that absolutely leads to program crash is:
while(agla!=NULL)
{
temp=NULL;temp->next=NULL;
You are setting a variable to NULL, then setting its fields. A null pointer points to nowhere, so you cannot edit its contents.
Remove temp->next=NULL;
Your program logic is not correct. You ruin the list after a few iterations of the loop and the program sticks in an infinite loop with mixed up pointers.
In bubble sort, we iterate through the items several times. In each iteration, the largest item is bubbled up to the end of the list. After first iteration, we are sure that the largest element is at the end of the list. After second iteration, we are sure that the second largest element is before the last element of the list, and so on.
You repeat this process until all the items are on their places:
int getListSize(Node* start)
{
int count = 0;
while(start != NULL)
{
count++;
start = start->next;
}
return count;
}
void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
int size = getListSize(start);
int i = 0;
while(size--)
{
Node
*current = start,
*prev = NULL; // We are at the beginnig, so there is no previous node.
while(current->next != NULL) // We have at least one node (size > 0) so `current` itself is not NULL.
{
Node *after = current->next;
if((*current) > (*after))
{
//swap the items
current->next = after->next;
after->next = current;
if (prev == NULL) // we are at the beginning
start = after;
else
prev->next = after;
prev = after;
}
else
{
prev = current;
current = current->next;
}
}
}
}
We repeat the "bubbling up" process size times. This is not the most efficient way, since we even compare the items that are already sorted. A more efficient way is to sort until no new swapping occurs:
void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
int size = getListSize(start);
int i = 0;
Node *lastSwapped = NULL;
while(size--)
{
Node
*current = start,
*prev = NULL, // We are at the beginnig, so there is no previous node.
*currentSwapped = NULL;
while(current->next != lastSwapped) // We have at least one node (size > 0) so `current` itself is not NULL.
{
Node *after = current->next;
if((*current) > (*after))
{
//swap the items
current->next = after->next;
after->next = current;
if (prev == NULL) // we are at the beginning
start = after;
else
prev->next = after;
prev = after;
currentSwapped = current;
}
else
{
prev = current;
current = current->next;
}
}
if (currentSwapped == NULL)
break; // No swapping occured. The items are sorted.
else
lastSwapped = currentSwapped;
}
}