Сортировка однонаправленного списка С++

102
21 ноября 2020, 08:50

помогите мне отсортировать список по имени, я понятия не имею как его нормально отсортировать.

    struct Worker // структура.
{
    string name;
    int rank;
    int yearOfBirth;
    int salary;
    Worker *next;
};

Вот что я пока начудил.

void printName(Worker* workers, int &size) // функция которая выводит на экран записи отсортированые по имени.
{
    Worker *min_worker = new Worker;
    Worker *time = new Worker;
    Worker *perv = new Worker;
    Worker *current = workers;
    for (int i = 0; workers != NULL; i++) {
        min_worker = workers;
        for (Worker *worker_k = workers; worker_k->next != NULL;) {
            if (min_worker->next->name[0] > worker_k->next->name[0]) {
                min_worker = worker_k;
            }
            perv = worker_k;
            worker_k = worker_k->next;
        }
        if (min_worker != workers) {
            /*swap(array[idx_i], array[min_idx]);*/
            time = min_worker;
            time->next = new Worker;
            current = time;
        }
        workers = workers->next;
    }
}
Answer 1

Тривиальным решением будет скопировать список в массив, отсортировать массив любым подходящим алгоритмом, после чего снова превратить его в список.

Но для непосредственной сортировки односвязных списков прекрасно подходит алгоритм MergeSort по стратегии снизу-вверх. См. https://ru.stackoverflow.com/a/433885/182825

Ваш код по-видимому является реализацией SelectionSort. И SelectionSort, и InsertionSort и BubbleSort тоже будут работать на односвязном списке.

Сразу бросаются в глаза, однако, какие-то бессмысленные действия

Worker *time = new Worker;
Worker *perv = new Worker;

являющиеся очевидными утечками памяти. Зачем вы выделяли эту память?

READ ALSO
Взаимодействие формы и виджета карты на ней

Взаимодействие формы и виджета карты на ней

Столкнулся с такой задачей как сделать форму, на которой, например, есть два виджета LineEdit и виджет карты (я взял QWebWidget и открыл в нем ЯндексКарты)

94
C++ atomic: ошибка LLVM из NDK

C++ atomic: ошибка LLVM из NDK

При включении любых C++ заголовков появляется ошибка в заголовках LLVM:

124
Отличить текст от ссылки

Отличить текст от ссылки

Есть форма ввода YouTubeВ неё можно ввести поисковой запрос или вставить ссылку на видео YouTube

129