связанный список сортировать функцию только петли один раз

Question

У меня есть связанный список, который я пытаюсь сортировать от наименьшего до наибольшего по цене. вот то, что я до сих пор

struct part { 
    char* name; 
    float price; 
    int quantity; 
    struct part *next; 
}; 

typedef struct part partType; 

partType *sort_price(partType **item) { 

    int check = 0;   

    if (*item == NULL || (*item)->next == NULL) 
     return *item; 
    else { 

     partType *temp1 = *item; 
     partType *temp2 = (*item)->next; 

     do{ 
     check = 0; 
     while (temp2 != NULL && temp2->next != NULL){ 
      if (temp2->price > temp2->next->price){ 
       temp1->next = temp2->next; 
       temp2->next = temp2->next->next; 
       temp1->next->next = temp2; 
       check = 1; 
      } 
      temp1 = temp2; 
      temp2 = temp2->next; 
     } 
     }while (check == 1); 
    } 
    return *item; 
} 

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

Answer 1

Вы используете только одну итерацию типа Bubble. Вам нужно повторить до тех пор, пока не будет прогон, который не имеет шансов на порядок ....

Обратите внимание, что у вас тоже есть ошибки ... Первый элемент не зависит от вашего алгоритма. поэтому, если я заберу 2->1, я бы получил 2->1 вместо 1->2. Аналогичным образом не влияет и на элемент temp1.

Так что, если я бегу на 4->3->2->1

t1= 4 ,t2 = 3, t2->next = 2 затем поменять t1= 4 ,t2 = 2, t2->next = 3

t1= 2 ,t2 = 3, t2->next = 1 затем поменять t1= 2 ,t2 = 1, t2->next = 3

И результат

4->2->1->3 

EDIT
Состояние хорошее. Добавить переменную changeOccured как

int changeOccured = 1; 
    while(changeOccured){ 
     changeOccured = 0; 
     // one run of bubble 
      if (temp2->price > temp2->next->price){ 
       //add this when the if succeed 
       changeOccured = 1; 
      } 

    } 

Answer 2

Вы можете использовать любые виды INPLACE как MergeSort.

Если вы знаете пространство клавиш, вы также можете пойти Counting Sort. Хорошая отправная точка. here

Answer 3

Если *item == NULL ваш пример аварии, так как вы получаете temp2перед тем проверить это.

И, конечно же, сортировать список в один проход невозможно, просто потому, что нет алгоритма линейной сортировки.

Вы можете разделить его и отсортировать рекурсивно (слияние сортировки). Это «будет выглядеть» как один прогон списка (слияние).