6 Replies - 8177 Views - Last Post: 09 February 2013 - 08:34 PM Rate Topic: -----

#1 Drpogue  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 18
  • Joined: 20-February 12

Sorting a doubly linked list in C

Posted 09 February 2013 - 07:11 PM

So I've written a doubly linked list but when I got to the sort method I started to suffer from heavy derptation.

#include<stdio.h>
#include<stdlib.h>
#include"list.h"
int i;
node *p;
node *n;

void insert(node *pointer, int data){
//go through list till ya find the last node
while(pointer->next!=NULL){
pointer = pointer->next;
}
//allocate memory for new node and put data in it
pointer->next = (node *)malloc(sizeof(node));
(pointer->next)->prev= pointer;
pointer = pointer->next;
pointer->data=data;
pointer->next = NULL;
}
void print(node *pointer){
if(pointer==NULL){
return;}
printf("%d ",pointer->data);
print(pointer->next);
}

int init(node *pointer,int find){
pointer =pointer->next;
while(pointer!=NULL){
if(pointer->data== find)//found find
{
printf("The data is in the list.");
return 1;
}
pointer = pointer->next;// Search in the next node.
}
//find is not found
printf("The data is not in the list.");
return 0;
}
void swap (node *x, node *y){
	int temp= x->data;
	x->data=y->data;
	y->data=temp;
}
void sort(node *pointer){
for(i=0;i<10;i++){
	if(pointer->data>pointer->next->data){
	}else{
		swap(pointer,pointer->next);
		}
		pointer=pointer->next;
	}
}




int main(){
//new is used to point to the first node
//temp is for the last node
node *new, *temp;
int z;
new=(node *)malloc(sizeof(node));
temp= new;
temp ->next = NULL;
temp ->prev = NULL;

for(z=0;z<10;z++){
insert(new,(3*10)-z);
}
init(new,12);
init(new,3);
init(new,27);
init(new,7);
print(new);
sort(new);
print(new);

}




The code should print out a list of 30 29 28 27 26 25 24 23 22 21, then when the sort is working sort the list 21 22 23 24 25 26 27 28 29 30. But it just prints out the list twice in descending order. Where did I got wrong?

Is This A Good Question/Topic? 0
  • +

Replies To: Sorting a doubly linked list in C

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10809
  • View blog
  • Posts: 40,288
  • Joined: 27-December 08

Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 07:54 PM

When dealing with Linked Lists, insertion sort or mergesort are really the algorithms you will want to implement. Bubblesort is expensive regularly, and algorithms that rely on lots of swaps become more inefficient when working with Linked Lists. Mergesort and Insertion Sort focus more on insertions than swaps. On top of that, when dealing with Linked Lists, mergesort doesn't require additional arrays when partitioning the List.
Was This Post Helpful? 0
  • +
  • -

#3 Drpogue  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 18
  • Joined: 20-February 12

Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:01 PM

EDIT

This post has been edited by Drpogue: 09 February 2013 - 08:10 PM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10809
  • View blog
  • Posts: 40,288
  • Joined: 27-December 08

Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:05 PM

I wouldn't describe this as a "Java" design. A bubblesort is a bubblesort, and it's fairly language agnostic. A note about spacing conventions though- you should work on them to make your code more legible.

Your algorithm really isn't a proper bubblesort. As baavgai advocates, it's not a bubblesort without a boolean. You also are missing the nested loops aspect.

Edit: Editing out your posts is a big no-no, by the way.
Was This Post Helpful? 0
  • +
  • -

#5 Drpogue  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 18
  • Joined: 20-February 12

Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:14 PM

View Postmacosxnerd101, on 10 February 2013 - 03:05 AM, said:

I wouldn't describe this as a "Java" design. A bubblesort is a bubblesort, and it's fairly language agnostic. A note about spacing conventions though- you should work on them to make your code more legible.

Your algorithm really isn't a proper bubblesort. As baavgai advocates, [url=http://www.dreamincode.net/forums/topic/231304-the-real-bubble-sort/]it's not a bubblesort without a boolean[/url]. You also are missing the nested loops aspect.

Edit: Editing out your posts is a big no-no, by the way.


All I was saying is that I tried to follow plans in a different language and apply them in one I don't know.Thank you for debating the finer points of data structures with me.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10809
  • View blog
  • Posts: 40,288
  • Joined: 27-December 08

Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:16 PM

Let's take a chill pill here. I'm not trying to berate you. I'm trying to get you going in the right direction. Your algorithm implementation is wrong, and I've told you why. I'm sorry that my help isn't appreciated.
Was This Post Helpful? 0
  • +
  • -

#7 Drpogue  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 18
  • Joined: 20-February 12

Re: Sorting a doubly linked list in C

Posted 09 February 2013 - 08:34 PM

I figured out the solution. Here is the code for any future users:

#include<stdio.h>
#include<stdlib.h>
#include"list.h"
int i;
node *p;
node *n;

void insert(node *pointer, int data){
//go through list till ya find the last node
while(pointer->next!=NULL){
pointer = pointer->next;
}
//allocate memory for new node and put data in it
pointer->next = (node *)malloc(sizeof(node));
(pointer->next)->prev= pointer;
pointer = pointer->next;
pointer->data=data;
pointer->next = NULL;
}
void print(node *pointer){
if(pointer==NULL){
return;}
printf("%d ",pointer->data);
print(pointer->next);
}

int init(node *pointer,int find){
pointer =pointer->next;
while(pointer!=NULL){
if(pointer->data== find)//found find
{
printf("The data is in the list.");
return 1;
}
pointer = pointer->next;// Search in the next node.
}
//find is not found
printf("The data is not in the list.");
return 0;
}
void swap (node *x, node *y){
    int temp= x->data;
    x->data=y->data;
    y->data=temp;
}
void sort(node*pointer){
	int i;
	while(pointer->next!=NULL){
if(pointer->data>pointer->next->data){
    swap(pointer,pointer->next);
    }
    pointer=pointer->next;
    sort(pointer);
    }
}








int main(){
//new is used to point to the first node
//temp is for the last node
node *new, *temp;
int z;
new=(node *)malloc(sizeof(node));
temp= new;
temp ->next = NULL;
temp ->prev = NULL;

for(z=0;z<10;z++){
insert(new,(3*10)-z);
}
init(new,12);
init(new,3);
init(new,27);
init(new,7);
print(new);
sort(new);
print(new);

}



Was This Post Helpful? 0
  • +
  • -

Page 1 of 1