Сортировка очень длинного связанного списка с помощью сортировки слиянием или быстрой сортировки в C - PullRequest
Новая
       108

Сортировка очень длинного связанного списка с помощью сортировки слиянием или быстрой сортировки в C

0 голосов
/ 04 марта 2019

Мне нужно реализовать знаменитую команду LS, я застрял, потому что я получаю очень длинный Linked-List для каждой папки, которую мне нужно отсортировать (ASCII, или время, или обратный порядок)

Здесьмоя структура связанного списка, 

 typedef struct     s_list
{
    void            *content;
    size_t          content_size;
    struct s_list   *next;
}                   t_list

Внутри void *content Я поместил свою структуру Ls, 

typedef struct      s_dir
{
    unsigned int    i;
    quad_t          blocks;
    char            *pathname;
    char            *name;
    ino_t           ino;
    uint8_t         type;
    uint16_t        mode;
    unsigned char   nlink;
    char            *usrname;
    char            *grpname;
    long long       size;
    time_t          time;
    struct s_dir    *rec;
    struct s_dir    *next;
    int             error;
}                   t_dir

В настоящее время я использую эту функцию для сортировки моего списка. 

static void             sort_ascii(t_list **head)
{
    t_dir   *rep;
    t_list  *curr;
    void    *tmp;
    t_dir   *rep_next;

    curr = *head;
    while (curr && curr->next && (rep = (t_dir *)curr->content)
            && (rep_next = (t_dir *)curr->next->content))
    {
        if (ft_strcmp(rep->pathname, rep_next->pathname) > 0)
        {
            tmp = curr->content;
            curr->content = curr->next->content;
            curr->next->content = tmp;
            curr = *head;
        }
        curr = curr->next;
    }
}

Моя проблема в том, что он невероятно медленный.

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

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

Спасибо за помощь!

1 Ответ

0 голосов
/ 04 марта 2019

Ваш код сортировки неверен: вы меняете поле content, но не content_size.Ожидается, что вы отсортируете элементы списка, обновив их next членов и обновив аргумент *head.

Ваш метод имеет квадратичную сложность, если не хуже.Вместо этого вы должны использовать сортировку слиянием, которая имеет гораздо меньшую временную сложность O (N.log (N)) .

Вот пример (сортировка слиянием сверху вниз): 

/* return the comparison status: 0 for equal, <0 if a < b, >0 if a>b */
int compare_ascii(t_list *a, t_list *b) {
    return ft_strcmp(((t_dir *)a->content)->pathname, ((t_dir *)b->content)->pathname);
}

t_list *merge(t_list *a, t_list *b, int (*cmp)(t_list *a, t_list *b)) {
    t_list *head = NULL;  /* head of the merged list */
    t_list **r = &head;   /* pointer to the node link */
    if (a && b) {
        for (;;) {
            if ((*cmp)(a, b) <= 0) {
                /* link the head node of list a */
                *r = a;
                r = &a->next;
                a = a->next;
                if (!a)
                    break;
            } else {
                /* link the head node of list b */
                *r = b;
                r = &b->next;
                b = b->next;
                if (!b)
                    break;
            }
        }
    }
    /* link the remaining part of a or b if any */
    *r = (a == NULL) ? b : a;
    return head;
}

t_list *mergesort(t_list *p, int (*cmp)(t_list *a, t_list *b)) {
    t_list *a, *b, *last = NULL;
    /* find the middle with 2 finger method: a moves twice as fast as b */
    for (a = b = p; a && a->next; a = a->next->next, b = b->next)
         last = b;
    if (last == NULL) {
        /* empty list or single element */
        return p;
    }
    /* split in the middle (before b) */
    last->next = NULL;
    /* sort each half and merge the sorted sublists */
    return merge(mergesort(p, cmp), mergesort(b, cmp), cmp);
}

void sort_ascii(t_list **head) {
    *head = mergesort(*head, compare_ascii);
}

Как прокомментировал rcgldr , сортировка по принципу слияния снизу обычно выполняется быстрее, потому что не нужно сканировать списки, чтобы найти средний элемент, что может быть дорого из-за несоответствия кеша.С другой стороны, он может выполнять больше сравнений, но все еще с временной сложностью O (N.log (N)) и не является рекурсивной.

Вот версия mergesortиспользуя сортировку слиянием снизу вверх: 

t_list *mergesort(t_list *head, int (*cmp)(t_list *a, t_list *b)) {
    t_list *array[32]; // sorted sublists: array[i] has 2**i length if not null
    t_list *result = head;
    int i, top = 0;

    // merge nodes into array
    while (result != NULL) {
        t_list *next = result->next;
        result->next = NULL;
        // merge sorted sublists by increasing power of 2 sizes
        for (i = 0; i < top && array[i] != NULL; i++) {
            result = merge(array[i], result, cmp);
            array[i] = NULL;
        }
        // store the merged list, update top, do not go past end of array
        if (i == top) {
            if (top < 32)
                top++;
            else
                i--;
        }
        array[i] = result;
        result = next;
    }
    // merge all sorted sublists into single list
    result = NULL;
    for (i = 0; i < top; i++) {
        result = merge(array[i], result, cmp);
    }
    return result;
}
...