Функция сортировки связного списка выполняется только один раз

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

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

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 затемswap 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

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

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

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

Answer 3

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

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