-
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();
}
-
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.
-
What is this line supposed to do?
Quote:
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.
-
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
-
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.