## problem sort a Doubly linked list

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### problem sort a Doubly linked list

i wrote this algorithm

Code: Select all
`node *current = last;   node *current2 = start;   for (int k = count ; k > 1 ; k-- ) {      node *max = new node;      max->value=0;      for (int j=1 ; j <= k ; j++) {         if ( max->value < current2->value )            max = current2;         current2 = current2->next;      }      current2 = start;      node *temp = current;      current = max;      current->next = max->next;      current->prev = max->prev;      max = temp;      max->next = temp->next;      max->prev = temp->prev;      current = temp->prev;      }`

but after i print it ... it look same ...

the nodes not changed

i dont know why

can u guys fix this or give me a better algorithm to sort a D LL
Placebo

Posts: 25
Joined: Tue Mar 10, 2009 12:13 pm

### Re: problem sort a Doubly linked list

Code: Select all
`      current->next = max->next;`

That code has some serious problems. You are using new but not delete, which right there should tell you that you have a memory leak. It happens as soon as you assign a value to max in the loop.

You should probably look into an algorithm called MergeSort. Implementing it for linked lists is not too hard, and it can be done without allocating any extra nodes. It's also in the fastest class of sorting algorithms, taking time O(n*log(n)) to complete.

Next time, please post a complete small program that we can test.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Re: problem sort a Doubly linked list

ok ... any solution about sorting?

can u give me a merge sort script for sorting this linked list?
Placebo

Posts: 25
Joined: Tue Mar 10, 2009 12:13 pm

### Re: problem sort a Doubly linked list

Placebo

Posts: 25
Joined: Tue Mar 10, 2009 12:13 pm

### Re: problem sort a Doubly linked list

Placebo wrote:ok ... any solution about sorting?

can u give me a merge sort script for sorting this linked list?

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Re: problem sort a Doubly linked list

huh .?? i dont know how it implement exactly

can u at least give me pseudo code?
Placebo

Posts: 25
Joined: Tue Mar 10, 2009 12:13 pm

### Re: problem sort a Doubly linked list

I gave you the name of the algorithm to use. http://lmgtfy.com/?q=mergesort

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Re: problem sort a Doubly linked list

ok another question

what exactly changed that my Linked list is doubly

whats the diff between sorting the single linked list with doubly linked list?
Placebo

Posts: 25
Joined: Tue Mar 10, 2009 12:13 pm

### Re: problem sort a Doubly linked list

Placebo wrote:ok another question

what exactly changed that my Linked list is doubly

whats the diff between sorting the single linked list with doubly linked list?

Hmmm... I can't think of any. The algorithm I would use works just fine for a singly linked list.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Who is online

Users browsing this forum: No registered users and 1 guest