Bubble sorting для связанного списка

Question

Bubble sorting для связанного списка

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

void sortBubble()
{
Node *i=start,*j=start;Node *temp;Node* prev=start;Node* agla;
while(i->next!=NULL)
{
cout<<"\nhello 1";
j=i;
agla=j->next;
while(agla!=NULL)
{
temp=NULL;temp->next=NULL;
cout<<"\nhello2";

if(*(j) > *(agla))
{
temp=agla->next;
agla->next=j;
prev->next=agla;
prev=agla;
agla=j->next;
j->next=temp;
}
else{
prev=j;
j=agla;
agla=j->next;}
}
prev=i;
i=i->next;
}
}
}

1

bubble-sort c++linked-list

Решение

Другие решения

Вы сравниваете элементы, просто делая *(j) > *(agla)Я не уверен, как это строит, так как оба j а также agla являются указателями на структуры. Структуры нельзя сравнивать напрямую.

0

Источник

Accepted Answer

Ваша первая очевидная ошибка, которая абсолютно приводит к сбою программы:

       while(agla!=NULL)
{
temp=NULL;temp->next=NULL;

Вы устанавливаете переменную в NULLзатем настройте его поля. Нулевой указатель указывает на никуда, поэтому вы не можете редактировать его содержимое.

Удалить temp->next=NULL;

Редактировать:

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

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

int getListSize(Node* start)
{
int count = 0;
while(start != NULL)
{
count++;
start = start->next;
}
return count;
}

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
int size = getListSize(start);
int i = 0;

while(size--)
{
Node
*current = start,
*prev = NULL; // We are at the beginnig, so there is no previous node.

while(current->next != NULL) // We have at least one node (size > 0) so `current` itself is not NULL.
{
Node *after = current->next;
if((*current) > (*after))
{
//swap the items
current->next = after->next;
after->next = current;
if (prev == NULL) // we are at the beginning
start = after;
else
prev->next = after;

prev = after;
}
else
{
prev = current;
current = current->next;
}
}
}
}

Мы повторяем процесс «пузырения» size раз. Это не самый эффективный способ, поскольку мы даже сравниваем уже отсортированные элементы. Более эффективный способ — сортировка, пока не произойдет новый обмен:

void bubbleSort(Node *&start) // <-- Pass a reference to pointer, because we may need to modify the start pointer.
{
int size = getListSize(start);
int i = 0;

Node *lastSwapped = NULL;

while(size--)
{
Node
*current = start,
*prev = NULL, // We are at the beginnig, so there is no previous node.
*currentSwapped = NULL;

while(current->next != lastSwapped) // We have at least one node (size > 0) so `current` itself is not NULL.
{
Node *after = current->next;
if((*current) > (*after))
{
//swap the items
current->next = after->next;
after->next = current;
if (prev == NULL) // we are at the beginning
start = after;
else
prev->next = after;

prev = after;
currentSwapped = current;
}
else
{
prev = current;
current = current->next;
}
}

if (currentSwapped == NULL)
break; // No swapping occured. The items are sorted.
else
lastSwapped = currentSwapped;
}
}

Это полная рабочая программа

1