Bubble Sort C - Liste Liée

Question

Voici donc le problème que j'ai avec ma petite fonction de tri à bulles. Je suis capable de trier la valeur mais je reçois toujours une coupure après 3 nœuds. Un exemple serait:

Trier les éléments suivants:

Je reçois toujours (du plus petit étant la tête):

Et c'est tout, rien d'autre.

void sortByLine (struct lnode** head) { 
     int count = 1; 
    while(count){ 
     struct lnode *temp =*head; 
    count = 0; 
    while(temp != NULL){ 
     struct lnode *next = nodeGetNext(temp); 
     if(next != NULL){   
      if((lineCmp(temp,next)) > 0){ 
      swap(head, next,temp); 
      count = 1; 
      } 
     } 
     temp = nodeGetNext(temp); 
    } 
} 

}

Ligne Cmp Fonction:

int lineCmp (struct lnode* n1, struct lnode* n2) { 
    int node1 = nodeGetLine(n1); 
    int node2 = nodeGetLine(n2); 

    if(node1 == node2){ 
     return 0; 
    } 
    else if(node1 > node2){ 
     return 1; 
    } 
    else 
     return -1; 

}

Fonction Swap:

void swap (struct lnode** head, struct lnode* n1, struct lnode* n2) { 
    struct lnode *prevn1 = nodeGetPrev(*head, n1); 
    struct lnode *prevn2 = nodeGetPrev(*head, n2); 

    struct lnode *nextn1 = nodeGetNext(n1); 
    struct lnode *nextn2 = nodeGetNext(n2); 

    if(prevn2 == n1 && prevn1 == NULL){ 
     evictNode(head, n2); 
     pushNode(head, n2); 
    } 
    else if(prevn1 == n2 && prevn2 == NULL){ 
     evictNode(head, n1); 
     pushNode(head, n1); 
    } 
    else if(prevn1 == n2 && nextn1 == NULL){ 
     evictNode(head, n1); 
     insertNode(head, prevn2 , n1); 
    } 
    else if(prevn2 == n1 && nextn2 == NULL){ 
     evictNode(head, n2); 
     insertNode(head, prevn1, n2); 
    } 
    else{ 
    evictNode(head, n1); 
    evictNode(head, n2); 
    insertNode(head, prevn2 , n1); 
    insertNode(head, prevn1 , n2); 
    } 

}

Answer 1

Votre problème est dans la fonction Swap: Suppression d'un nœud peut invalider les nœuds calculés précédents

void swap (struct lnode** head, struct lnode* n1, struct lnode* n2) { 
    struct lnode *prevn1 = nodeGetPrev(*head, n1); 
    struct lnode *prevn2 = nodeGetPrev(*head, n2); 

    struct lnode *nextn1 = nodeGetNext(n1); 
    struct lnode *nextn2 = nodeGetNext(n2); 

    if(prevn2 == n1 && prevn1 == NULL){ 
     evictNode(head, n2); 
     pushNode(head, n2); 
    } 
    else if(prevn1 == n2 && prevn2 == NULL){ 
     evictNode(head, n1); 
     pushNode(head, n1); 
    } 
    else if(prevn1 == n2 && nextn1 == NULL){ 
     evictNode(head, n1); 
     insertNode(head, prevn2 , n1); 
    } 
    else if(prevn2 == n1 && nextn2 == NULL){ 
     evictNode(head, n2); 
     insertNode(head, prevn1, n2); 
    } 
    else if (n1==prevn2) 
    { 
     evictNode (head, n1); 
     insertNode(head, n2, n1); 
    } 
    else if (n2==prevn1) 
    { 
     evictNode (head, n2); 
     insertNode(head, n1, n2); 
    } 
    else { 
    evictNode(head, n1); 
    evictNode(head, n2); 
    insertNode(head, prevn1, n2); 
    insertNode(head, prevn2, n1); 
    } 
}