Thread: Help with simple program to bubble sort the values of a linked list

Hello everyone,

I have been tasked with creating a program which (1) takes in integer values from a user (until the user enters -1) and inputs these values into a linked list. This (2)original list is then to be printed out. The program then uses the algorithm "bubble sort" to (3)order the list in descending order before finally printing it out again.

I have managed to do this but I kind of cheated since I do not quite understand how to manipulate a linked list. What did was I took the values in the linked list and transferred them into an array and then did bubble sort on that array.

I was hoping someone could explain how to do bubble sort on a linked list as well as how to print a linked list.

Thanks in advance.

Here is my code:

Code:

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


typedef struct node
{
    int info;
    struct node *link;
    
}Node, *NodePointer;


void printList (NodePointer head)
{
    int counter=0;
    NodePointer temp=head;
    while(temp!=NULL)
    {
        /*printf("%d\n",temp->info);*/
        temp=temp->link;
        counter++;
        
    }
    
    int*array[counter];
    int counter2=0;
    NodePointer temp2=head;
    while(temp2!=NULL)
    {
        array[counter2]=temp2->info;
        temp2=temp2->link;
        counter2++;
        
    }
    int i;
    for(i=counter-1;i>=0;i--)
    {
        printf("%d\n",array[i]);
    }
    int o,j,temp4;
///////////////////////////////////////////
//Here I preform bubble sort on array//
///////////////////////////////////////////
    for(o=counter-1;o>=1;o--)
    {
        for(j=0;j<=o-1;j++)
        {
            if(array[j]>array[j+1])
            {
                temp4=array[j];
                array[j]=array[j+1];
                array[j+1]=temp4;
                
                
            }
        }
    }
    printf("Sorted List: \n");

    for(i=counter-1;i>=0;i--)
    {
        printf("%d\n",array[i]);
    }
}
NodePointer newNode(int i, NodePointer np)
{
    NodePointer p =(NodePointer)malloc(sizeof(Node));
    if (p==NULL)
    {
        printf("\n Out of Memory");
    }
    else
    {
        p->info=i;
        p->link=np;
    }
    return p;
}




NodePointer insertAtFront (int item, NodePointer head)
{
    return newNode (item,head);
}
int main(void)
{
    NodePointer list=NULL;
    int num=0;
    while(num!=-1)
    {    
    printf("Enter Number (-1 to finish): ");
    scanf("%d",&num);
    if(num!=-1)
    {
    list=insertAtFront(num,list);
    }
    }
    printf("Original List: \n");
    printList(list);
    
    
    return 0;
}

I was hoping someone could explain how to do bubble sort on a linked list as well as how to print a linked list.

Using bubble sort on a linked list is probably the worst choice one can make. Merge sort is both faster than it and easier to implement than it for linked lists.

In order to print a linked list, the list needs to be built correctly: that is, each node points to the next. Then, you use a loop to assign each node to an extra variable in turn, and print that variable. In most implementations, it comes down to something like this:

Code:

for (list_node *i = head; i != NULL; i = i->next) {
   display(i->data);
}

Display would be a function (real or imaginary) that takes the information in data and displays it on the screen. Not all lists work like this though. In particular, NULL doesn't have to be at the end of the list, but I can guarantee that something is, and the logic is the same.

If you do need to do a bubble sort on a linked list, you just have to swap the pointers. It's best if you sit down with a piece of paper, draw a linked list of (say) five items, and then figure out how you would swap the (say) second and fourth items just by erasing the arrows and drawing new ones.

"It's best if you sit down with a piece of paper, draw a linked list of (say) five items, and then figure out how you would swap the (say) second and fourth items just by erasing the arrows and drawing new ones."

In my head I understand how it would work but the trouble is I do not know how to implement it with code.

Originally Posted by NDP

"It's best if you sit down with a piece of paper, draw a linked list of (say) five items, and then figure out how you would swap the (say) second and fourth items just by erasing the arrows and drawing new ones."

In my head I understand how it would work but the trouble is I do not know how to implement it with code.

Every time you re-draw an arrow you are re-setting one of your links. You should perhaps note the relationship between which nodes you want to swap and which nodes you are drawing new arrows on.