bubble sorting in linked list

This is a discussion on bubble sorting in linked list within the C Programming forums, part of the General Programming Boards category; hi everyone i am trying to sort a linked list using bubble sort method but i couldn't reach its end. ...

  1. #1
    anu
    anu is offline
    Registered User
    Join Date
    Oct 2001
    Posts
    9

    bubble sorting in linked list

    hi everyone

    i am trying to sort a linked list using bubble sort method but i couldn't reach its end. i need ur help to get it.

    following is a simple bubble sort program with an array

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

    void bubble(int x[]);

    int main() {
    int data[]={4,7,6,8,3};
    bubble(data);
    return 0;
    }

    void bubble(int x[])
    {
    int i, j, temp;
    for(i=0;i<=3;i++)
    {
    for(j=0;j<=3;j++)
    {
    if (x[j]>x[j+1])
    {
    temp=x[j];
    x[j]=x[j+1];
    x[j+1]=temp;
    }

    }
    }

    printf("after sorting.....\n");
    for(i=0;i<=4;i++)
    printf(" %d\n",x[i]);
    }

    and, the attached file is linked list program where i am trying to use bubble sorting.
    Attached Files Attached Files

  2. #2
    Unregistered
    Guest
    Use a double linked list. They are so much cleaner to work with. Much easier to move around.

    Actually...

    Don't bother moving the nodes. Just swap their contents. This would be the easiest thing to do. Just treat it like an array. Still, I'd go for a double link list here too. Thus:

    temp = node->value;
    node->value = node->prev->value;
    node->prev->value = temp;

    That'd be all you needed to do to swap the node contents around. Now then, if you actually have something externally pointing to a node already, you couldn't use the value swap, you'd actually have to reorder the nodes.

    Either way, a double linked list is the way to go.

    Quzah.

  3. #3
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    void bubble(int x[])
    {
    int i, j, temp;
    for(i=0;i<=3;i++)
    {
    for(j=0;j<=3;j++)
    {
    if (x[j]>x[j+1])
    {
    temp=x[j];
    x[j]=x[j+1];
    x[j+1]=temp;
    }
    This may work but bubble sort loops should look more like this:
    Code:
    #include<stdio.h>
    void bubble(int[],int);
    int main()
    {
    	int array[] = {6,3,22,4,111,5};
    	int i;
    
    	bubble(array,sizeof(array)/sizeof(array[0]));
    	
    	for(i=0;i < sizeof(array)/sizeof(array[0]); i++)
    	{
    		printf("%d ", array[i]);
    	}
    	return 0;
    }
    
    void bubble(int a[], int size)
    {
    	int temp;
    	for(int i = 0; i < size; i++)
    	{
    		for(int ii = 0; ii < size; ii++)
    		{
    			if(a[i] < a[ii])
    			{
    				temp = a[i];
    				a[i] = a[ii];
    				a[ii] = temp;
    			}
    		}
    	}
    }
    Now also I know that if you want to use bubble sort on a linked list than you must pass the list into the function rather than an array. I don't want to give this example because I have too much to do today. If you get really stuck than I can help at some point this week though.

  4. #4
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Jesus wait a minute. I did that loop wrong!!! LOL, hold on.

  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Code:
    void bubble(int a[], int size)
    {
    	int temp;
    	for(int i = 0; i < size; i++)
    	{
    		for(int ii = i + 1; ii < size; ii++)
    		{
    			if(a[i] > a[ii])
    			{
    				temp = a[i];
    				a[i] = a[ii];
    				a[ii] = temp;
    			}
    		}
    	}
    }
    You confused me. The main difference is that the second loop is:
    int ii = i + 1. This is more natural.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  2. sorting linked list
    By bazzano in forum C Programming
    Replies: 1
    Last Post: 05-20-2006, 05:33 AM
  3. Sorting Linked List Problem
    By chriscolden in forum C Programming
    Replies: 8
    Last Post: 01-17-2006, 09:46 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21