Как отсортировать список с пузырьковой сортировки в C++

Question

У меня есть этот класс:

class Elem 
{ 
public: 
    int x; 
    Elem *nast; 
}; 

У меня есть конструктор по умолчанию, функция, чтобы показать x. Я сделал список из десяти элементов, но как отсортировать этот список, упорядоченный по x?

Я попытался это:

void Sortlinked_list(Elem *head) 
{ 
    int ile = 0; 
    Elem *cur; 
    cur = head; 
    while(cur->nast != NULL) 
    { 
     cur = cur->nast; 
     ile++; 
    } 

    Elem* curr = head; 
    Elem* next; 
    int temp; 

    for(int i = 0; i < ile; i++) 
    { 
     while(curr && curr->nast) 
     { 

      next = curr->nast; 
      while (next) 
      { 
       if (curr->show() > next->show()) 
       { 
        std::swap(next->nast, curr->nast); 
       } 
       next = next->nast; 
      } 
      curr = curr->nast; 
     } 
    } 
} 

Но это не работает. Выход: http://i.stack.imgur.com/vJrRK.png

Если кто-нибудь может мне помочь? Я провел 3 часа и ничего не делал.

Answer 1

Кажется, у алгоритма есть проблема.

Рассмотрим:

7 -> 3 -> 5 

В первом контуре cur пунктов до 7 и указывает на next 3, так что будет подкачки из nast указателей.

После обмена cur->nast будет указывать на 5, в то время как next->nast указывает на 3, что само по себе. Итак, цепь сломана, и элемент 3 потерян.

7 -> 5 
3 -> 3 

Другими словами - только замена из nast указателей не будет достаточно.

Answer 2

Вот простой подход к реализации функции. Функция просто свопирует элементы данных x соседних элементов.

void sort(Elem * &head) 
{ 
    Elem *first = head; 
    Elem *last = nullptr; 

    while (first && first->nast != last) 
    { 
     Elem *sorted = first->nast; 
     for (Elem *current = first; current->nast != last; current = current->nast) 
     { 
      if (current->nast->x < current->x) 
      { 
       std::swap(current->nast->x, current->x); 
       sorted = current->nast; 
      }     
     } 
     last = sorted; 
    } 

    head = first; 
} 

Answer 3

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

Тогда возникает проблема, если один из узлов является первым узлом в списке, который имеет указатель на голову. и/или последний узел в списке, который имеет указатель на хвост.

Простейшей альтернативой является использование двух списков (нужен только второй указатель на узел, первоначально NULL). Удалите узел из исходного списка и вставьте его по порядку во второй изначально пустой список.