problem sort a Doubly linked list

[Placebo]

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

[Alvaro]

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.

[Placebo]

ok ... any solution about sorting?

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

[Placebo]

[Alvaro]

ok ... any solution about sorting?

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

No. Do your own homework.

[Placebo]

huh .?? i dont know how it implement exactly

can u at least give me pseudo code?

[Alvaro]

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

[Placebo]

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?

[Alvaro]

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.