Реализация mergesort в связанном списке

Question

Мне было поручено реализовать алгоритм сортировки слияния в списке, написанном на C/C++. У меня есть общая идея, написал мой код и успешно скомпилировал его. Однако, когда я запустил его, он начнется нормально, но затем введет «подготовленный список, теперь начинаю сортировку» без каких-либо ошибок. Я попытался просмотреть свой код, но у меня полная потеря относительно того, что может быть проблемой. Я также довольно дилетантский с отладкой, поэтому использование gdb в меру своих способностей не привело меня туда. Любые советы или советы будут огромной помощью, спасибо всем!

#include <stdio.h> 
#include <stdlib.h> 

struct listnode 
{ 
    struct listnode *next; 
    int key; 
}; 

    //Finds length of listnode 
int 
findLength (struct listnode *a) 
{ 
    struct listnode *temp = a; 
    int i = 0; 
    while (temp != NULL) 
    { 
     i++; 
     temp = temp->next; 
    } 
    return i; 
} 


struct listnode * 
sort (struct listnode *a) 
{ 
    // Scenario when listnode is NULL 
    if (findLength (a) <= 1) 
     return a; 

    //Find middle 
    int mid = findLength (a)/2; 
    struct listnode *temp = a; 
    struct listnode *first = a; 
    struct listnode *second; 

    for (int i = 0; i < mid - 1; i++) 
    { 
     temp = a->next; 
    } 
    second = temp->next; 
    temp->next = NULL; 

    //Recursive calls to sort lists 
    first = sort (first); 
    second = sort (second); 

    if (first != NULL && second != NULL) 
    { 
     if (first->key < second->key) 
     { 
      a = first; 
      first = first->next; 
     } 
     else 
     { 
      a = second; 
      second = second->next; 
     } 
    } 

    struct listnode *head = a; 
    struct listnode *tail = a; 

    while (first != NULL && second != NULL) 
    { 
     if (first->key < second->key) 
     { 
      tail = first; 
      first = first->next; 
      tail = tail->next; 
     } 
     else 
     { 
      tail = second; 
      second = second->next; 
      tail = tail->next; 
     } 
    } 

    if (first == NULL) 
    { 
     while (second != NULL) 
     { 
      tail = second; 
      second = second->next; 
      tail = tail->next; 
     } 
    } 

    while (first != NULL) 
    { 
     tail = first; 
     first = first->next; 
     tail = tail->next; 
    } 

    return a; 
} 

Вот код теста при условии, написанный в C: INT

main (void) 
{ 
    long i; 
    struct listnode *node, *tmpnode, *space; 
    space = (struct listnode *) malloc (500000 * sizeof (struct listnode)); 
    for (i = 0; i < 500000; i++) 
    { 
     (space + i)->key = 2 * ((17 * i) % 500000); 
     (space + i)->next = space + (i + 1); 
    } 
    (space + 499999)->next = NULL; 
    node = space; 
    printf ("\n prepared list, now starting sort\n"); 
    node = sort (node); 
    printf ("\n checking sorted list\n"); 
    for (i = 0; i < 500000; i++) 
    { 
     if (node == NULL) 
     { 
      printf ("List ended early\n"); 
      exit (0); 
     } 
     if (node->key != 2 * i) 
     { 
      printf ("Node contains wrong value\n"); 
      exit (0); 
     } 
     node = node->next; 
    } 
    printf ("Sort successful\n"); 
    exit (0); 
} 

Answer 1

Вы близко, но с некоторыми глупыми ошибками. Проверьте операции добавления на шаге слияния. Они не делают то, что вы думаете. И, конечно, вы означали temp = temp->next; в цикле разделения.

Если gdb является подавляющим, добавление printf - отличный способ сделать этот отладочный код. Фактически вы хотите написать функцию печати списка и распечатать подсписки на каждом уровне рекурсии плюс результаты шага слияния. Приятно наблюдать. Просто будьте аккуратны и удалите все это, когда закончите.

Вот код, который работает для справки:

struct listnode *sort(struct listnode *lst) { 
    if (!lst || !lst->next) return lst; 
    struct listnode *q = lst, *p = lst->next->next; 
    while (p && p->next) { 
    q = q->next; 
    p = p->next->next; 
    } 
    struct listnode *mid = q->next; 
    q->next = NULL; 
    struct listnode *fst = sort(lst), *snd = sort(mid); 
    struct listnode rtn[1], *tail = rtn; 
    while (fst && snd) { 
    if (fst->key < snd->key) { 
     tail->next = fst; 
     tail = fst; 
     fst = fst->next; 
    } else { 
     tail->next = snd; 
     tail = snd; 
     snd = snd->next; 
    } 
    } 
    while (fst) { 
    tail->next = fst; 
    tail = fst; 
    fst = fst->next; 
    } 
    while (snd) { 
    tail->next = snd; 
    tail = snd; 
    snd = snd->next; 
    } 
    tail->next = NULL; 
    return rtn->next; 
} 

На мой старый MacBook это сортирует 10 миллионов случайных чисел в чуть более 4 секунд, что, кажется, не так уж плохо.

Вы также можете поместить операцию на добавление в макрос и сделать это довольно кратким:

struct listnode *sort(struct listnode *lst) { 
    if (!lst || !lst->next) return lst; 
    struct listnode *q = lst, *p = lst->next->next; 
    while (p && p->next) { 
    q = q->next; 
    p = p->next->next; 
    } 
    struct listnode *mid = q->next; 
    q->next = NULL; 
    struct listnode *fst = sort(lst), *snd = sort(mid); 
    struct listnode rtn[1], *tail = rtn; 
    #define APPEND(X) do { tail->next = X; tail = X; X = X->next; } while (0) 
    while (fst && snd) if (fst->key < snd->key) APPEND(fst); else APPEND(snd); 
    while (fst) APPEND(fst); 
    while (snd) APPEND(snd); 
    tail->next = NULL; 
    return rtn->next; 
} 

Answer 2

ли это быть сверху вниз сортировка слиянием? Чтобы вы начали, вот частичное исправление, не проверялось на другие вещи. | if (first! = NULL & & second! = NULL) | проверка не требуется, так как предварительная проверка на длину < = 1 позаботится об этом, но это не вызовет проблемы.

while (first != NULL && second != NULL) 
    { 
     if (first->key < second->key) 
     { 
      tail->next = first; 
      tail = first; 
      first = first->next; 
     } 
     else 
     { 
      tail->next = second; 
      tail = second; 
      second = second->next; 
     } 
    } 

    if (first == NULL) 
    { 
     tail->next = second; 
    } 
    else 
    { 
     tail->next = first; 
    } 
}