Bubble Sort C - Связанный список

Question

Итак, вот проблема, с которой я сталкиваюсь с моей функцией сортировки мелких пузырьков. Я могу сортировать значение, однако я всегда получаю отсечку после трех узлов. Примером может быть:

Сортировка следующее:

Я всегда получаю (от наименьшего будучи головой):

И все, ничего.

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); 
    } 
} 

}

Линия Cmp Функция:

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; 

}

Своп Функция:

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

Вашей проблема заключается в свопе функции: Удаление узла может привести к недействительности предыдущих расчетных узлов

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); 
    } 
}