Сортировка вставками для сортировки узлов в LinkedList

Я пытаюсь использовать метод сортировки вставками для сортировки узлов из LinkedList. Я так много раз корректировал код, но не могу понять его, продолжаю получать разные типы результатов, которые не отсортированы.

Вот код:

Node* sort_list(Node* head)
{
    Node* node_ptr = NULL;
    for(Node* i = head->next; i->next != NULL; i = i->next){
            if (i->key < head->key) {
                node_ptr = i;
                head = head->next;
    }
    }
    return node_ptr;
}

c++ nodes linked-list insertion-sort
person Manny O    schedule 24.10.2013    source источник
comment
Найдите похожие вопросы, подобные этому здесь, чтобы помочь твое понимание.   -  person miqh    schedule 24.10.2013
comment
Fwiw, это также не выполняет сортировку вставками (или любую другую сортировку, которую можно описать). По своему определению сортировка вставками имеет сложность O(NlogN) именно потому, что нижний сегмент использует бинарный поиск для определения места следующего элемента, который должен быть вставлен в уже отсортированную подпоследовательность, задача, не слишком простая со связанными списки, но тривиально с контейнерами с произвольным доступом.   -  person WhozCraig    schedule 24.10.2013

Ответы (1)


arrow_upward
0
arrow_downward

Это домашнее задание, поэтому вместо прямого написания кода я сначала укажу, где вы ошиблись.

В алгоритме сортировки вставки, очевидно, должна быть какая-то замена, которую необходимо выполнить между элементами, которые находятся не на своем месте (которые необходимо вставить). Поэтому начните с размышлений о том, как поменять местами два элемента массива. Обратите особое внимание на случаи, когда одна голова или одна хвост.

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

Далее вы должны подумать о случаях, когда нам нужно сортировать. В данном случае это довольно просто. Если текущий элемент и следующий за ним отсортированы (в порядке возрастания, текущий ‹ следующий). Тогда ничего не нужно делать, а просто сделать следующий текущим.

Тогда вы, очевидно, можете сделать вывод, что нарушение этого случая - это когда вам нужно поменять местами элементы. После замены (с должным вниманием к тому, где были и будут указатели после сортировки) повторяйте процесс, пока не упретесь в нулевую стену.

PS: Это возможный дубликат другого вопроса SO.

person rajaditya_m    schedule 24.10.2013