Пузырьковая сортировка по односвязному списку Наихудшая сложность по времени? - PullRequest
Новая
       42

Пузырьковая сортировка по односвязному списку Наихудшая сложность по времени?

0 голосов
/ 26 мая 2020

Я знаю, что односвязный список указывает только на следующее значение и не может указывать на предыдущее значение, поэтому я прав, думая, что при пузырьковой сортировке список будет действовать так же, как массив, где он идет только в одном направление? Если бы это было так, сложность времени была бы O (n ^ 2)?

Ответы [ 2 ]

2 голосов
/ 26 мая 2020 
#include <iostream> 

struct Node
{
    int data;
    struct Node* next;
} Node;


struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
    struct Node* tmp = ptr2->next;
    ptr2->next = ptr1;
    ptr1->next = tmp;
    return ptr2;
}


int bubbleSort(struct Node** head, int count)
{
    struct Node** h;
    int i, j, swapped;

    for (i = 0; i <= count; i++)
    {

        h = head;
        swapped = 0;

        for (j = 0; j < count - i - 1; j++)
        {

            struct Node* p1 = *h;
            struct Node* p2 = p1->next;

            if (p1->data > p2->data)
            {


                *h = swap(p1, p2);
                swapped = 1;
            }

            h = &(*h)->next;
        }


        if (swapped == 0)
            break;
    }
}
/* Function to print the list */
void printList(struct Node* n)
{
    while (n != NULL)
    {
        std::cout << n->data << " -> ";
        n = n->next;
    }
    std::cout << std::endl;
}

void insertAtTheBegin(struct Node** start_ref, int data)
{
    struct Node* ptr1
        = (struct Node*)malloc(sizeof(struct Node));

    ptr1->data = data;
    ptr1->next = *start_ref;
    *start_ref = ptr1;
}

//------------------------------------------- Driver Code 
int main()
{
    int arr[] = { 80,34,232,22,50,6 };
    int list_size, i;

    struct Node* start = NULL;
    list_size = sizeof(arr) / sizeof(arr[0]);

    for (i = 0; i < list_size; i++)
        insertAtTheBegin(&start, arr[i]);

    std::cout << "Linked list before sorting\n";
    printList(start);

    bubbleSort(&start, list_size);

    std::cout << "Linked list after sorting\n";
    printList(start);

    return 0;
}

Как видите, пузырьковая сортировка в списке имеет ту же временную сложность, что и пузырьковая сортировка в массиве, но с той лишь разницей, что временная сложность равна квадратичной c.

0 голосов
/ 26 мая 2020

Да, это будет.

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

...