Linked List Sorting

This is a discussion on Linked List Sorting within the C Programming forums, part of the General Programming Boards category; I am trying to sort a linked list, and output the results. But I am having a very difficult time ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    1

    Linked List Sorting

    I am trying to sort a linked list, and output the results. But I am having a very difficult time doing so. As of now my program is failing to even display anything.

    Basically I have created a small linked list with a few numbers in it, and am trying to switch around the pointers in it so that its sorted.

    I don't know any other way to sort a linked list, but I am looking for the simplest way to sort these. I do not care about speed / optimization as long as it gets sorted and I understand how to do it. Here is my code, please take a look. Thanks!

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <ctype.h>
    
    main()
    {
        struct node{
            int value;
            struct node *next;
    		struct node *previous;
        };
    	int n = 0;
    	int change = 1;
    	struct node *traveling_node;
    	struct node *last_created = NULL;
    	struct node *new_node;
    	struct node *last;
    	struct node *next_next;
    	struct node *temp;
    	
    	new_node = malloc(sizeof(struct node));
    	(*new_node).value = 20;
    	new_node->next = NULL;
    	last_created = new_node;
    
    	for (n = 1; n < 20; n++)
    	{
    		new_node = malloc(sizeof(struct node));
    		new_node->value = (100%n)*(n+1);
    		new_node->next = last_created;
    		last_created = new_node;
    	}
    	new_node = malloc(sizeof(struct node));
    	new_node->value = 50;
    	new_node->next = last_created;
    	last_created = new_node;
    
    	traveling_node = new_node;
    	while ((change == 1) && (traveling_node != NULL))
    	{
    		next_next = traveling_node->next;
    		if ((traveling_node->value) > (next_next->value))
    		{
    			temp = traveling_node;
    			traveling_node = next_next;
    			next_next = temp;
    		}
    		else
    		{
    			if(traveling_node == NULL)
    				change = 0;
    		}
    		next_next = traveling_node->next;
    		traveling_node->next; 
    	}
    	traveling_node = new_node;
    	printf("Forward ");
    	while(traveling_node != NULL)
    	{
    		printf("%d ", traveling_node->value);
    		traveling_node = traveling_node->next;
    
    	}
    	printf("\n");
    	getchar();
    	getchar();
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You should consider breaking this up into functions. You might consider making a function that takes a list and returns a sorted one.
    Code:
    struct node *sortlist( struct node *l )
    {
    }
    Make a loop that takes the top node from the list, and adds it to a secondary list. When you add it, make sure you walk through the new list, and put it where it goes in the list. Repeat until you run out of nodes in the list you pass. Now return the new list's top node.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    What is this line supposed to do?
    traveling_node->next;
    Hint: It does nothing

    So, what algorithm are you trying to use. I don't know any list sorting algorithms that work with just a single loop, no recursive calls, and no inner loops, passing once through a list, and I have implemented 27 different linked-list sorting algorithms.

  4. #4
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    I would really guess the algorithm works. I guess u are trying to use bubble sort. The actual algorithm is not right. you need 2 pointer to sort the array one is i and i+1(j).

    In your case have a pointer to the first node and the another pointer which traverse alway down the tree swaping the nodes on condition satisfied.

    Have a look at this tutorial http://en.wikipedia.org/wiki/Bubble_sort

    ssharish2005

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Bubble Sort is actually not quite as easy on a singly-linked list as it is on an array.

    Insertion sort is the simplest for a singly-linked-list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 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