help by sorting a simply linked list
 

Hi!
Pls, somebody help me!! I'm stuck here since days. I don't know, what i'm doing wrong.

Re: help by sorting a simply linked list
 

Hello,

I looked at your code, and it appears to be a bubble-sort. Here is what I would do.

1) Get yourself a nice sheet of paper, and a pencil.

2) Draw out your data structure.

[CODE]

+-------+ +------------------+ +------------------+
| head | | data | point | | data | point |
+-------+ +------------------+ +------------------+

[\CODE]

Remember to draw little boxes for the temp pointers and stuff too.

3) Go through your code by hand, and fill in the paper as the computer would during the iterations. Do not assume when doing this by hand. Go through the motions, and stick with it. You will find your error.

4) In my coding days, I was always sure to make a duplicate head pointer, just in case I messed up the transition somewhere. Guess it was mild parinoia.

Christian

Re: help by sorting a simply linked list
 

Hello my brother
there is two way to sort a single linked list
First , swapping data but it is unsufficient (( suppose the data is very bug))
Second, swapping pointer is better but it's harder
here you are the two ways
Swapping the pointers

void Sortable_List::sort()

{

        Node *ptr1,*ptr2,*temp,*Imithead1,*Imithead2,*before;

        if (head != NULL) {

                ptr2 = head;

                ptr1 = head->next;

                //First Step Set the smallest value to head

                while(ptr1 != NULL ) {

                        if (ptr2->data > ptr1->data ) {

                                temp = ptr2;

                                while(temp->next != ptr1) 

                                        temp = temp->next;

                                temp->next = ptr1->next;

                                ptr1->next = ptr2;

                                head = ptr1;}

                        ptr1 = ptr1->next;

                        ptr2 = head;}

                

////////////////////////////////////////////

////////////////////////////////////////////

                before = head;

                Imithead1 = Imithead2 = head->next;

                while (Imithead1 != NULL) {

                        

                while (Imithead2 != NULL ) {

                        ptr1 = ptr2 =Imithead2;

                        while(ptr1 != NULL ) {

                                if (ptr2->data > ptr1->data ) {

                                        temp = ptr2;

                                        while(temp->next != ptr1) 

                                                temp = temp->next;

                                        before->next = ptr1;

                                        temp->next = ptr1->next;

                                        ptr1->next = ptr2;

                                        Imithead2 = ptr1;

                        

                                }

                                ptr1 = ptr1->next;

                                ptr2 = Imithead2;

                        }

                        before = Imithead2;

                        Imithead2 = Imithead2->next;

                        

                }

                

                Imithead1 = Imithead1->next;

                Imithead2 = Imithead1;

                }



                

        }

        

        

}

Swapping Data

        NodeEmp *Ptr1,*Ptr2;

        Ptr1 = Ptr2 = Emp;

        if (Emp != NULL && Emp->next != NULL){

                while (Ptr1 != NULL)

                {                

                        Ptr2= Ptr1;

                             while(Ptr2!= NULL){

                        swap(Ptr1,Ptr2);                                

                        Ptr2 = Ptr2->next;                                

                }

                Ptr1 = Ptr1->next;

                }

        }

Re: help by sorting a simply linked list
 

Thanks to all people that replied.
I finally found the solution. I'm posting the method for sorting below:

void List::listsort(){

  element *p, *n, *flag, *anterior;

  bool sortiert;

  do {

    p = head;

    n = head -> next;

    for (int i = 0; i< anzahl; i++) {

      if (p -> nummer < n -> nummer) {

        p = n;

        n = n-> next;

        sortiert = 1;

      } else {

        //jetzt wird geordnet

        sortiert = 0;

        flag = n;

        p -> next = flag -> next; //p (tail) mußt zu 0 zeigen. Bevor: p -> n -> 0

        n -> next = p; //n -> p statt n -> 0



        anterior = head;

        for (int j=1; j<i; j++) { //damit j=1 wird in eine vor p gehalten

          anterior = anterior -> next; //anterior wird bewegt genau vor p (anterior -> p -> n -> 0)

        }

        anterior -> next = n; //damit wird anterior Nachfolgers n



        if (p -> next == 0) {  //d.h. tail!!!!

          tail = p;

          n -> next = tail;

          number = (tail -> nummer) + 1; //der nächste nummer von tail

        }       else {

        n = n -> next -> next;

        }

        //        p = head;

        //      n = head -> next;

      }

    }

  } while (!sortiert);

}

P..S. i live in germany and this programm is for the university of münchen. Therefore, the comments are in german. And also, i come from ecuador, so my mother language is spanish. So, anterior means previous.