Bubble Sorting a Linked List

**Sankait Laroiya** · 10-10-2014

Hello guys,
I wrote a code to bubble sort the elements of a linked list and its below. I couldn't understand how to apply bubble sort to a list so I copied the list's nodes into an array and applied bubble sort on that array (traditional method).
I was curious whether this code is 'EFFICIENT', like a good programming practice?
And how to apply bubble sort directly to linked list?

Here's the code:

Code:

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

// --- FUNCTION PROTOTYPES ---
void create_node();
void remove_newline();
char append();
void display();

// GLOBAL VARIABLES
int x=1;
int array[9];
// --- LIST ---
struct numbers
{
   int num;
   struct numbers *next;
};

struct numbers *first_node;
struct numbers *current_node;
struct numbers *new_node;
struct numbers *temp;
struct numbers *array_node;


int main()
{


    printf("Hello!, input the numbers: \n");

    first_node=(struct numbers *)malloc(sizeof(struct numbers));
    if(first_node== NULL)
    {
        puts("Memory allocation failed!");
        return(0);
    }
    current_node=first_node;
    printf("Input the #%d value: ", x);
    scanf("%d", &current_node->num);

    remove_newline();
    char choice=append();

    while(choice == 'y' || choice== 'Y')
     {
         x++;
         create_node();
         remove_newline();
         choice = append();
         if( choice == 'n' || choice == 'N')
         {
             current_node->next=NULL;
             new_node->next=NULL;
             printf("Okay, then. Bye\n");

         }
     }

     display();
     printf("\nTOTAL NUMBER OF NODES: %d",x);
     putchar('\n');


     // --- LIST TO ARRAY ---

     int i,array[x];

     array_node=first_node;
     for(i=0;i<x;i++)
     {
         array[i]= (array_node->num);
         array_node=array_node->next;
     }

     // --- BUBBLE SORT ---
     printf("Bubble sorted: \n");
     int outer,inner,tmp;
     for(outer=0;outer<x-1;outer++)
     {
         for(inner=outer+1;inner<x;inner++)
         {
             if(array[outer]>array[inner])
             {
                 tmp=array[outer];
                 array[outer]=array[inner];
                 array[inner]=tmp;
             }
         }
     }

     for(i=0;i<x;i++)
     {
         printf("%d\t",array[i]);
     }



     return(0);
}

//--- FUNCTIONS ---

void create_node()
{
    new_node=(struct numbers*)malloc(sizeof(struct numbers));
    current_node->next=new_node;
    if(new_node==NULL)
    {
        puts("Memory allocation failed");
    }
        current_node=new_node;
        printf("Input #%d number: \n",x);
        scanf("%d",&current_node->num);
}

void remove_newline()
{
    while(getchar() != '\n')
        ;
}

char append()
{
    printf("\nDo you want to add more numbers in the list? Y/N: ");
    char choice;
    scanf("%c", &choice);
    putchar('\n');
    return(choice);
}

void display()
{
    printf("Here is the list: \n");

    temp=first_node;
    while(temp!= NULL)
    {
        printf("%d\t",temp->num);
        temp=temp->next;
    }
}

Thanks.

EDIT: Yes I know that I shouldn't typecast malloc()

**stahta01** · 10-10-2014

Global variables are consider bad practice.

NOTE: EFFICIENT and bubble sort are NOT normally used together.

Tim S.

**jimblumberg** · 10-10-2014

First do you realize that you're using a VLA in the following snippet:

Code:

int x=1;
...
    while(choice == 'y' || choice== 'Y')
     {
         x++;
 ...
 
 
     // --- LIST TO ARRAY ---
 
     int i,array[x];  // Note the non compile time constant array size.

To answer your question, IMO, if you want the information in your list sorted you'd probably be better off inserting them in this sorted order.

Jim

**stahta01** · 10-10-2014

I would have used the idea of insertion sort and created a second link list.
NOTE: Sorting the first link list in place would likely be considered more EFFICIENT by some measures; but, it is harder to do.

Tim S.

**rcgldr** · 10-10-2014

Note that you could have sorted the nodes by creating an array of pointers to those nodes in the linked list and sorting via the pointers. Implementing a bubble sort with a single linked list could be done by repeatedly moving the "largest" node to the end of the list, then removing that node from the list and inserting it at the beginning of a the "currently sorted" list, using a second list pointer. When completed, the original list pointer would be NULL and the second list pointer would point to the first node of the sorted list.

**anduril462** · 10-10-2014

Originally Posted by Sankait Laroiya

EDIT: Yes I know that I shouldn't typecast malloc()

Then why the heck are you still doing it? Clearly we've told you that before. How do you think we feel about volunteering our little bit of free time and energy giving advice and help to people that don't listen to us?

Originally Posted by Sankait Laroiya

Hello guys,
I wrote a code to bubble sort the elements of a linked list and its below. I couldn't understand how to apply bubble sort to a list so I copied the list's nodes into an array and applied bubble sort on that array (traditional method).
I was curious whether this code is 'EFFICIENT', like a good programming practice?
And how to apply bubble sort directly to linked list?

Bubble sort is not efficient no matter what the data type (the "smart" version that bails out if no swaps were made is only efficient when the data is already sorted). Sure it's not horrible, but it's not very good. Insertion/selection sorts would do a bit better for linked lists, but still not great. Merge sort (IIRC bottom-up in particular) is pretty good.

Something I will mention that you should consider general advice that applies to all your questions, not just this one:
You are almost certainly not the first person to wonder about this or ask this question. There's likely a fair amount of research and information about this out there; you should try doing some research first. A Google search for "sorting a linked list" would be a great place to start.

**rcgldr** · 10-10-2014

Originally Posted by anduril462

Merge sort (IIRC bottom-up in particular) is pretty good.

Using an array of 32 (or less) list pointers where the number of nodes in arrray[i] is 2^i, and merging nodes into the array, then merging the array is probably the fastest method. In addition to the array, you need two working list pointers, one for one of the merge input parameters, and one for merge output. This is how it's implemented in std::list::sort in Microsoft STL.

**Sankait Laroiya** · 10-11-2014

Some modifications as suggested:

Code:

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

// --- FUNCTION PROTOTYPES ---
void create_node();
void remove_newline();
char append();
void display();
void bubble_sort(int *array);

// --- GLOBAL VARIABLES ---
int x=1;

// --- LIST ---
struct numbers
{
   int num;
   struct numbers *next;
};

struct numbers *first_node;
struct numbers *current_node;
struct numbers *new_node;
struct numbers *temp;
struct numbers *array_node;


int main()
{


    printf("Hello!, input the numbers below: \n\n");

    first_node=malloc(sizeof(struct numbers));
    if(first_node== NULL)
    {
        puts("Memory allocation failed!");
        return(0);
    }
    current_node=first_node;
    printf("Input the #%d value: ", x);
    scanf("%d", &current_node->num);

    remove_newline();
    char choice=append();

    while(choice == 'y' || choice== 'Y')
     {
         x++;
         create_node();
         remove_newline();
         choice = append();
     }
    if( choice == 'n' || choice == 'N')
         {
             current_node->next=NULL;
             new_node->next=NULL;
             printf("Okay, then. Bye\n\n");

         }
    else
    {
        printf("Invalid Input!");
        return(0);
    }

     display();
     printf("\n\nTOTAL NUMBER OF NODES: %d\n\n",x);

     // --- LIST TO ARRAY ---
     int i,*array[x];

     array_node=first_node;
     for(i=0;i<x;i++)
     {
         array[i]= (int *)(array_node->num);
         array_node=array_node->next;
     }

     bubble_sort((int *)array);

    // --- DISPLAY SORTED ARRAY ---
     for(i=0;i<x;i++)
     {
         printf("%d\t",(int)array[i]);
     }



     return(0);
}

//--- FUNCTIONS ---

void create_node()
{
    new_node=malloc(sizeof(struct numbers));
    current_node->next=new_node;
    if(new_node==NULL)
    {
        puts("Memory allocation failed");
    }
        current_node=new_node;
        printf("Input #%d number: \n",x);
        scanf("%d",&current_node->num);
}

void remove_newline()
{
    while(getchar() != '\n')
        ;
}

char append()
{
    printf("\nDo you want to add more numbers in the list? Y/N: ");
    char choice;
    scanf("%c", &choice);
    putchar('\n');
    return(choice);
}

void display()
{
    printf("Here is the list: \n");

    temp=first_node;
    while(temp!= NULL)
    {
        printf("%d\t",temp->num);
        temp=temp->next;
    }
}

void bubble_sort(int *array)                   // --- BUBBLE SORT ---
{
     printf("Bubble sorted: \n");
     int outer,inner,tmp;
     for(outer=0;outer<x-1;outer++)
     {
         for(inner=outer+1;inner<x;inner++)
         {
             if(array[outer]>array[inner])
             {
                 tmp=array[outer];
                 array[outer]=array[inner];
                 array[inner]=tmp;
             }
         }
     }
}

Removed unwanted global variables.
Used array of pointers to convert list data into array.
Moved bubble sort into seperate function.
Removed typecasting for malloc().

Originally Posted by stahta01

Global variables are consider bad practice.

NOTE: EFFICIENT and bubble sort are NOT normally used together.

Tim S.

I had to declare structure global because it went into more than one different function. And I used x to count those nodes so I declared it global. I removed the other one and tried to minimize the use of global variables.

Originally Posted by jimblumberg

First do you realize that you're using a VLA in the following snippet

Yes, I realize. I did it so because I wanted to make sure that the size of array needed to sort the list is equal to the number of nodes.

**Sankait Laroiya** · 10-11-2014

Originally Posted by anduril462

Then why the heck are you still doing it? Clearly we've told you that before. How do you think we feel about volunteering our little bit of free time and energy giving advice and help to people that don't listen to us?

Please don't go all angry over me. I wrote the code some time ago. Then I didn't know that malloc() doesn't need to be typecasted always. If you want to share your knowledge, you are welcome. I appreciate what people do by helping others in this forum and If I wanted to ignore you then I wouldn't even have mentioned that line. Thanks and no offense intended.

Originally Posted by anduril462

Bubble sort is not efficient no matter what the data type (the "smart" version that bails out if no swaps were made is only efficient when the data is already sorted). Sure it's not horrible, but it's not very good. Insertion/selection sorts would do a bit better for linked lists, but still not great. Merge sort (IIRC bottom-up in particular) is pretty good.

I haven't learnt any other sorts yet. So, I used this one.

Originally Posted by anduril462

Something I will mention that you should consider general advice that applies to all your questions, not just this one:
You are almost certainly not the first person to wonder about this or ask this question. There's likely a fair amount of research and information about this out there; you should try doing some research first. A Google search for "sorting a linked list" would be a great place to start.

You don't realize how much I try to solve the problem before coming here. You think I come here ranting about my problems without trying to solve them myself in first place,well, you are wrong. I am an infant in programming (study level: 12th grade) and if you don't humbly want to help, then what are you doing here. I appreciate the time you spent to help me, but you are not supposed to boss over the people you help. So, shut it on that one.
Again, I don't want to offend you or disrespect you. Thanks.

**stahta01** · 10-11-2014

I think learning to bubble-sort a link list is a waste of time.
You should instead as I suggested before re-write the link list to support insertion sort.

FYI: You are using C casts a lot; this is often a sign of design or implementation mistakes.

Tim S.

**jimblumberg** · 10-11-2014

Yes, I realize. I did it so because I wanted to make sure that the size of array needed to sort the list is equal to the number of nodes.

Do you also realize that VLA are not supported with all/most compilers? And that VLA are only truly supported by the C99 C standard, they are not allowed in previous standards and are optional in the later C standards?

I really recommend you think about using "normal" dynamic memory (malloc/free) if you really desire this functionality.

Jim

**Sankait Laroiya** · 10-11-2014

Originally Posted by stahta01

I think learning to bubble-sort a link list is a waste of time.
You should instead as I suggested before re-write the link list to support insertion sort.

FYI: You are using C casts a lot; this is often a sign of design or implementation mistakes.

Tim S.

When I learn other sorts I will leave bubble sort.
At two instances I got warnings from my IDE. It said that I was trying to assign a an in from a pointer, so I typecasted the pointer to int so the warnings disappeared. I usually donot typecast in my code.

**Sankait Laroiya** · 10-11-2014

Originally Posted by jimblumberg

Do you also realize that VLA are not supported with all/most compilers? And that VLA are only truly supported by the C99 C standard, they are not allowed in previous standards and are optional in the later C standards?

I really recommend you think about using "normal" dynamic memory (malloc/free) if you really desire this functionality.

Jim

Then in my code the array under LIST TO ARRAY comment will be allocated memory like so? Right? :

Code:

int *array = malloc(sizeof(int) *x) ;

and this pointer will be incremented with array++?
And could you please elaborate the problem behind assigning an array its size during runtime?
Thanks.

**jimblumberg** · 10-11-2014

At two instances I got warnings from my IDE. It said that I was trying to assign a an in from a pointer, so I typecasted the pointer to int so the warnings disappeared. I usually donot typecast in my code.

Casting to avoid compiler warnings is usually not a good idea. And the following is IMO a very poor use of the cast.

Code:

     // --- LIST TO ARRAY ---
     int i,*array[x];

     array_node=first_node;
     for(i=0;i<x;i++)
     {
         array[i]= (int *)(array_node->num);
         array_node=array_node->next;
     }

     bubble_sort(array);

Why is array a pointer to an array of int in the first place? And since the array[x] is a VLA that makes things even worse.

Jim

**Sankait Laroiya** · 10-11-2014

Originally Posted by jimblumberg

Casting to avoid compiler warnings is usually not a good idea. And the following is IMO a very poor use of the cast.

Code:

     // --- LIST TO ARRAY ---
     int i,*array[x];

     array_node=first_node;
     for(i=0;i<x;i++)
     {
         array[i]= (int *)(array_node->num);
         array_node=array_node->next;
     }

     bubble_sort(array);

Why is array a pointer to an array of int in the first place? And since the array[x] is a VLA that makes things even worse.

Jim

array_node->num is an int and to avoid warning I typecasted it to an int pointer and assigned it to int array.
How would you suggest to modify it?

Thread: Bubble Sorting a Linked List

Thread Tools

Search Thread

Display

Bubble Sorting a Linked List

Similar Threads

Bubble sorting singly link list

bubble sort in a linked list

Linked list bubble sort

bubble sorting in linked list

bubble sorting in linked list