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

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

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

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

Поскольку оба алгоритма работают за O (n * log n), принятие обоснованного решения потребует профилирования их обоих на машине, на которой вы хотите их запустить. .

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

Я решил проверить свою гипотезу и написал C-программу, которая измеряла время (используя clock () ), затрачиваемое на сортировку связанного списка целых чисел. Я попытался использовать связанный список, в котором каждый узел был выделен с помощью 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 секунд

Заключение:

По крайней мере, на моей машине копирование в массив стоит того, чтобы улучшить производительность кэша, поскольку в реальной жизни у вас редко бывает полностью упакованный связанный список. Следует отметить, что на моей машине Phenom II с тактовой частотой 2,8 ГГц, а ОЗУ только 0,6 ГГц, поэтому кэш очень важен.

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

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

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

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

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

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

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

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

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

Сортировка слиянием - лучшее, что вы можете сделать здесь.

Сортировка слиянием не требует доступа 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 );
}