Программирование на C - вставка сортируется в односвязном списке

Question

Я почти закончил с моим назначением, последняя часть - написать функцию, которая сортирует односвязный список с помощью сортировки вставкой. Я также связан предопределенными структурами и typedefs моего назначения:

struct le {
    int value;
    struct le *next;
};

typedef struct le listenelement;
typedef listenelement *list;

Те, которые я не могу изменить. Функция сортировки вставок должна работать с этими параметрами. Если параметр m отрицателен, предполагается, что список отсортирован в порядке убывания, а в противном случае - в порядке возрастания.

void sort(int m, list *l);

РЕДАКТИРОВАТЬ:

Вот моя попытка реализовать ответы отсюда.. Я до сих пор не могу заставить его работать. Я попытался создать новый список, который является конечным результатом с именем "asc" (для отсортированного по возрастанию списка) и знакомым списком "aux", но я застрял...

void sort(int m, list *l){              
    if ((m == 0) || (*l == NULL)) {
        printf("Error.\n");
    } else {
        if (m>0) {
            listenelement head = {0,NULL};              
            list asc = {&head};
            list aux = *l;
            while (aux != NULL) {                       
                int val = aux->value;                                                   
                delete_elem(val,&aux);                                                  
                while ((asc->next != NULL) && ((asc->value)<val)) {         
                    printf("%d\n", (asc->value));                                       
                    asc=asc->next;
                }
                insert(val,&asc);   
                asc = &head;                            
            }
            *l = &head;
        }
    }
}

Answer 1

сортировка вставок не может работать в односвязном списке, не так ли? Вы можете только идти вперед в них.

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

Сортировка вставки повторяется, потребляя один входной элемент за каждое повторение и увеличивая отсортированный список вывода. Каждая итерация, сортировка вставкой, удаляет один элемент из входных данных, находит его местоположение в отсортированном списке и вставляет его туда. Повторяется до тех пор, пока не останется никаких элементов ввода.

Обратите внимание, что эта характеристика не зависит от порядка, в котором вы можете проходить элементы. Вы застряли на обычной реализации шага вставки, который включает в себя итерацию назад по списку, чтобы найти позицию вставки. На самом деле вы могли бы сделать это с помощью своего односвязного списка, в смысле тестирования каждого предыдущего элемента от ближайшего к наиболее удаленному, но это изменило бы общую асимптотическую сложность алгоритма на O (N³). Нехорошо. И не обязательно.

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

Главное, что отличается, это лучшие сценарии и сценарии. Наилучший случай для обычной реализации - это то, что элементы изначально расположены по порядку, а наихудший случай - то, что они изначально в обратном порядке. Они просто перевернуты для наивной реализации подхода итерации-вперед, но со связанным списком и тщательной реализацией эти два случая могут быть сделаны почти одинаково хорошими. Реализация с повторением в обратном направлении имеет некоторые дополнительные практические последствия для массивов, но они не применяются к связанным спискам.