пузыря сортировки связанного списка в C

Question

Я создал связанный список из 5 узлов типа:

typedef struct node 
{ 
    int i; 
    struct node* link; 
}node; 

node* head = NULL; 

При распечатке, это дает:

4 3 2 1 0 

Указатель головки устанавливается в точку в 4. Затем я написал функцию для создания пузырьков связанного списка следующим образом:

void sort(void) 
{ 
    node* cur = head; 
    node* next = cur->link; 
    node* prev = NULL; 

    while(cur->i > next->i) 
    { 
     printf("cur is greater than next\n"); 

     while(prev != head) 
     { 
      cur->link = next->link; 
      next->link = cur; 
      head = next; 
      next = cur->link; 
      prev = head; 
     } 
     while(next != NULL) 
     { 
      prev->link = next; 
      cur->link = next->link; 
      next->link = cur; 
      prev = next; 
      next = cur->link; 
     } 
     printf("second while loop exited\n"); 

     for (node* ptr = head; ptr != NULL; ptr = ptr->link) 
     { 
      printf("%d", ptr->i); 
     } 

     cur = head; 
     next = cur->link; 

     } 
} 

Существуют различные заявления printf для che ck, что программа работает. Что я нахожу в том, что после первого прогона, 4 успешно ое следующим образом:

3 2 1 0 4 

Однако после повторной установки указателя текущ 3 и рядом с 2, следующим прогоном обеспечивает следующее:

2 1 0 4 3 

в конечном счете, мы закончим с

0 4 3 2 1 

Итак, как можно видеть "3", "2" и "1" в настоящее время ыми слишком далеко. Я попробовал различные условия вместо третьего цикла, чтобы исправить это, но в большинстве случаев это приводит к сегрегациям. Конечно, другое дело в том, что моя логика может быть совершенно неправильной, и может быть лучший способ реализовать это. Не могли бы вы просто сменить содержимое узлов, а не самих указателей? Любая помощь приветствуется. Заранее спасибо

Answer 1

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

Связанный список обрабатывается исключительно последовательно, поэтому он не допускает такой простой оптимизации без добавления искусственного «индекса», увеличиваемого по итерации списка. Вот почему это легче перебирать всегда через весь список и заканчивается, когда не были заменены не более элементов, следовательно, список отсортирован:

void sort(void) 
{ 
    int swapped = 1; 

    while(swapped) 
    { 
     node **prev = &head, *curr, *next; 

     swapped = 0; 
     for(curr = head; curr; prev = & curr->link, curr = curr->link) 
     { 
      next = curr->link; 

      if(next && curr->i > next->i) 
      { 
       curr->link = next->link; 
       next->link = curr; 
       *prev = next; 

       swapped = 1; 
      } 
     } 
    } 
} 

EDIT - некоторые объяснения в ответе на вопросы в комментариях Matthew2015.

Логические условия в C ожидают выражения с числами или указателями, которые считаются «истинными», если они отличны от нуля или отличаются от NULL соответственно. Это означает, что while(swapped) по существу эквивалентен while(swapped != 0) и next && ... эквивалентен next != NULL && ....Условие в while(swapped != 0) означает, что цикл завершится, когда некоторое выполнение внутреннего for не установит swapped в 1, что происходит, когда ни один элемент в списке больше, чем его преемник, то есть когда список сортируется.

for выражение условия цикла равно curr, что эквивалентно curr != NULL. Это заставляет цикл for проходить по списку до тех пор, пока не будет «текущего» узла.

Переменная переменной node **prev указывает на указатель, указывающий на текущий узел. Когда нужно заменить текущий и следующий узел, ссылка «предыдущая» больше не должна указывать на «текущий» узел, а на «следующий» узел. Конечно, можно сохранить указатель на «предыдущий узел» и присвоить новое значение (previous node)->link, но это не сработает в случае первого узла в списке, который не имеет «предыдущего узла», но на него указывает head переменная. Необходимо использовать дополнительное условие для проверки того, является ли текущий узел первым узлом для устранения этой несогласованности. Имея указатель на указатель, который первоначально указывает на head, а затем на 'previous node'.link, весь код намного проще, короче, а также немного быстрее.

Answer 2

я смотрел бы на третьем while

while(next != NULL) 
    { 
     prev->link = next; 
     cur->link = next->link; 
     next->link = cur; 
     prev = next; 
     next = cur->link; 
    } 

Здесь вы всегда движущихся элементов без проверки, есть ли они быть перемещены - т.е. cur->i > next->i.

Кстати, если это охранник правда, второй while получает выполняется только один раз, и таким образом это то же самое, как if, так что я хотел бы использовать if, по крайней мере, по причинам ясности.