Какой самый быстрый алгоритм сортировки связанного списка?

в зависимости от ряда факторов, это может быть быстрее, чтобы скопировать список в массив и затем использовать Quicksort.

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

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

- - - EDIT

Я решил проверить свою гипотезу и написал C-программу, которая измеряла время (используя clock()) принято сортировать связанный список ints. Я пробовал со связанным списком, где каждый узел был выделен с malloc() и связанный список, где узлы были выложены линейно в массиве, так что производительность кэша будет лучше. Я сравнил их со встроенным qsort, который включал копирование всего из фрагментированного списка в массив и копирование результата обратно. Каждый алгоритм выполнялся на тех же 10 наборах данных и результаты усреднялись.

вот результаты:

N = 1000:

фрагментированный список с сортировкой слиянием: 0.000000 секунд

массив с qsort: 0.000000 секунд

упакованный список с сортировкой слиянием: 0.000000 секунд

N = 100000:

фрагментированный список с сортировкой слиянием: 0.039000 секунд

массив с qsort: 0.025000 секунд

упакованный список с сортировкой слиянием: 0.009000 секунд

N = 1000000:

фрагментированный список с сортировкой слиянием: 1.162000 секунды

массив с qsort: 0.420000 секунд

упакованный список с сортировкой слиянием: 0.112000 секунд

N = 100000000:

фрагментированный список с сортировкой слиянием: 364.797000 секунд

массив с qsort: 61.166000 секунд

упакованный список с сортировкой слиянием: 16.525000 секунд

вывод:

по крайней мере на моей машине, копирование в массив дорогого стоит для повышения производительности кэша, так как вы редко имеете полностью упакованный связанный список в реальной жизни. Следует отметить, что моя машина имеет 2.8 GHz Phenom II, но только 0.6 GHz RAM, поэтому Кэш очень важен.

сравнение сортов (т. е. те, которые основаны на сравнении элементов) не может быть быстрее, чем n log n. Не имеет значения, какова базовая структура данных. Смотрите Википедия.

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

Как уже неоднократно говорилось, нижняя граница сортировки на основе сравнения для общих данных будет O (N log n). Чтобы кратко резюмировать эти аргументы, есть n! различные способы сортировки списка. Любое дерево сравнения, которое имеет n! (который находится в O(n^n)) возможные окончательные сорта будет нужен по крайней мере log (n!) как его высота: это дает вам нижнюю границу O(log(n^n)), которая является O(N log n).

Итак, для общих данных в связанном списке, наилучшая возможная сортировка, которая будет работа над любыми данными, которые могут сравнивать два объекта, будет O (N log n). Однако, если у вас есть более ограниченная область вещей для работы, вы можете улучшить время, которое требуется (по крайней мере, пропорционально n). Например, если вы работаете с целыми числами не больше некоторого значения, вы можете использовать Подсчет Вроде или Radix Sort, поскольку они используют конкретные объекты, которые вы сортируете, чтобы уменьшить сложность с пропорцией к n. будьте осторожны, хотя они добавляют некоторые другие вещи к сложности, которую вы можете не учитывать (например, сортировка подсчета и сортировка по радиусу добавляют факторы, основанные на размере чисел, которые вы сортируете, O(n+k), где k-размер наибольшего числа для сортировки подсчета, например).

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

Это хорошая небольшая статья на эту тему. Его эмпирический вывод заключается в том, что Treesort является лучшим, а затем Quicksort и Mergesort. Сортировка осадка, сортировка пузыря, сортировка выбора выполняют очень плохо.

СРАВНИТЕЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ СОРТИРОВКИ СВЯЗАННЫХ СПИСКОВ чин-Куан Шэнь

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981

A Radix sort особенно подходит для связанного списка, так как легко сделать таблицу головных указателей, соответствующих каждому возможному значению цифры.

сортировка слиянием не требует доступа O(1) и является O ( n ln n ). Нет известных алгоритмов сортировки общих данных лучше, чем O ( n ln n ).

специальные алгоритмы данных, такие как сортировка по радиусу ( ограничение размера данных ) или сортировка гистограммы ( подсчет дискретных данных), могут сортировать связанный список с более низкой функцией роста, если вы используете другую структуру с доступом O(1) в качестве временного хранилища.

другой класс специальных данных-это сравнение почти отсортирован список с k элементами не по порядку. Это можно отсортировать в операциях O ( kn).

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

например, учитывая связанный список, содержащий uint_8, этот код будет сортировать его в O (N) времени с помощью гистограммы сортировки:

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

typedef struct _list list_t;
struct _list {
    uint8_t value;
    list_t  *next;
};


list_t* sort_list ( list_t* list )
{
    list_t* heads[257] = {0};
    list_t* tails[257] = {0};

    // O(N) loop
    for ( list_t* it = list; it != 0; it = it -> next ) {
        list_t* next = it -> next;

        if ( heads[ it -> value ] == 0 ) {
            heads[ it -> value ] = it;
        } else {
            tails[ it -> value ] -> next = it;
        }

        tails[ it -> value ] = it;
    }

    list_t* result = 0;

    // constant time loop
    for ( size_t i = 255; i-- > 0; ) {
        if ( tails[i] ) {
            tails[i] -> next = result;
            result = heads[i];
        }
    }

    return result;
}

list_t* make_list ( char* string )
{
    list_t head;

    for ( list_t* it = &head; *string; it = it -> next, ++string ) {
        it -> next = malloc ( sizeof ( list_t ) );
        it -> next -> value = ( uint8_t ) * string;
        it -> next -> next = 0;
    }

    return head.next;
}

void free_list ( list_t* list )
{
    for ( list_t* it = list; it != 0; ) {
        list_t* next = it -> next;
        free ( it );
        it = next;
    }
}

void print_list ( list_t* list )
{
    printf ( "[ " );

    if ( list ) {
        printf ( "%c", list -> value );

        for ( list_t* it = list -> next; it != 0; it = it -> next )
            printf ( ", %c", it -> value );
    }

    printf ( " ]\n" );
}


int main ( int nargs, char** args )
{
    list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" );


    print_list ( list );

    list_t* sorted = sort_list ( list );


    print_list ( sorted );

    free_list ( list );
}

Не прямой ответ на ваш вопрос, но если вы используете Пропустить, он уже отсортирован и имеет время поиска O(log N).

Как я знаю, лучший алгоритм сортировки - O(n*log n), независимо от контейнера-было доказано, что сортировка в широком смысле слова (стиль mergesort/quicksort и т. д.) не может идти ниже. Использование связанного списка не даст вам лучшего времени выполнения.

единственный алгоритм, который работает в O (n), - это алгоритм "взлома", который основан на подсчете значений, а не на фактической сортировке.

Mergesort-это лучшее, что вы можете сделать здесь.

вот реализация который проходит по списку только один раз, собирая запуски, а затем планирует слияния таким же образом, что и mergesort.

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

для этого требуется o(log m) временная память; сортировка выполняется на месте в списках.

(обновлено ниже. комментатор один делает хороший момент, что я должен описать его здесь)

суть алгоритма:

    while list not empty
        accumulate a run from the start of the list
        merge the run with a stack of merges that simulate mergesort's recursion
    merge all remaining items on the stack

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

проще всего просто вставить код слияния здесь:

    int i = 0;
    for ( ; i < stack.size(); ++i) {
        if (!stack[i])
            break;
        run = merge(run, stack[i], comp);
        stack[i] = nullptr;
    }
    if (i < stack.size()) {
        stack[i] = run;
    } else {
        stack.push_back(run);
    }

рассмотрим сортировку списка (d a g i b e c f j h) (игнорирование запусков). Состояния стека выполняются следующим образом:

    [ ]
    [ (d) ]
    [ () (a d) ]
    [ (g), (a d) ]
    [ () () (a d g i) ]
    [ (b) () (a d g i) ]
    [ () (b e) (a d g i) ]
    [ (c) (b e) (a d g i ) ]
    [ () () () (a b c d e f g i) ]
    [ (j) () () (a b c d e f g i) ]
    [ () (h j) () (a b c d e f g i) ]

затем, наконец, объединить все эти списки.

обратите внимание, что количество элементов (запусков) в стеке[i] равно нулю или 2^i, а размер стека ограничен 1+log2(nruns). Каждый элемент объединяется один раз на уровне стека, следовательно, o(n log m) сравнения. Есть передавая сходство с Timsort здесь, хотя Timsort поддерживает свой стек, используя что-то вроде последовательности Фибоначчи, где это использует степени двух.

накопление запусков использует все уже отсортированные данные, так что лучшая сложность случая-O(n) для уже отсортированного списка (один запуск). Поскольку мы накапливаем как восходящие, так и нисходящие прогоны, прогоны всегда будут иметь длину не менее 2. (Это уменьшает максимальную глубину стека по крайней мере на один, оплачивая стоимость поиска трасс в первое место.) В худшем случае сложность O (N log n), как и ожидалось, для данных, которые сильно рандомизированы.

(Хм... Второе обновление.)

или просто посмотреть Википедию на "снизу-вверх" сортировка слиянием.