Связанные списки Bubble Sort

Question

Мне интересно, как реализовать пузырьковую сортировку в односвязном списке. Скажем, например, что у нас есть список, состоящий из следующих узлов:

struct node {
   int value;
   struct node* next;
}

Я считаю, что есть два способа сделать это:

1)to directly exchange `values` in memory
2)to change `nexts`, to point to a different nodes

Какой способ более эффективен, и может ли кто-нибудь дать мне пример того, как это сделать? Мне известно, что использование Bubble Sort не очень эффективно по сравнению с другими алгоритмами сортировки.

Answer 1

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

Answer 2

Вы должны рассмотреть различные особые случаи, если вы обменяете nexts.Это делает его немного медленнее, чем изменение value с.Если ваши значения имеют большую структуру, у вас есть возможность реализовать next -версию или заменить значение указателем.