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

Мне любопытно, является ли O (n log n) лучшим, что может сделать связанный список.

Разумно ожидать, что вы не сможете добиться большего, чем O (N log N), по времени выполнения .

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

Саймон Тэтхам, известный специалист по Putty, объясняет, как отсортировать связанный список с помощью сортировки слиянием . В заключение он дает следующие комментарии:

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

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

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

Как упоминает @ Jørgen Fogh ниже, нотация big-O может скрывать некоторые постоянные факторы, которые могут привести к тому, что один алгоритм будет работать лучше из-за локальности памяти, из-за малого количества элементов и т. Д.

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

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

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

Поскольку оба алгоритма работают за 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. Не имеет значения, какова основная структура данных. См. Википедию .

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

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

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

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

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

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

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

Сортировка слиянием не требует доступа 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), независимо от контейнера - было доказано, что сортировка в широком смысле слова (стиль слияния / быстрой сортировки и т. Д.) Не может быть ниже. Использование связанного списка не улучшит время работы.

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

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

Сложность равна O (n log m), где n - количество элементов, а m - количество прогонов. В лучшем случае O (n) (если данные уже отсортированы), а в худшем - O (n log 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);
    }

Рассмотрите возможность сортировки списка (dagibecfjh) (игнорируя запуски). Состояния стека выполняются следующим образом:

    [ ]
    [ (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), как и ожидалось, для сильно рандомизированных данных.

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

Или просто посмотрите википедию по восходящей сортировке слиянием .

Вы можете скопировать его в массив, а затем отсортировать.

• Копирование в массив O (n),

• сортировка O (nlgn) (если вы используете быстрый алгоритм вроде сортировки слиянием),

• копирование обратно в связанный список O (n) при необходимости,

так что это будет O (nlgn).

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

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

Вопрос в LeetCode # 148 , и есть множество решений, предлагаемых на всех основных языках. Моя такова, но меня интересует временная сложность. Чтобы найти средний элемент, мы каждый раз просматриваем полный список. nПовторяются элементы в первый раз, элементы повторяются во второй раз 2 * n/2, и так далее и так далее. Вроде O(n^2)пора.

def sort(linked_list: LinkedList[int]) -> LinkedList[int]:
    # Return n // 2 element
    def middle(head: LinkedList[int]) -> LinkedList[int]:
        if not head or not head.next:
            return head
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

    def merge(head1: LinkedList[int], head2: LinkedList[int]) -> LinkedList[int]:
        p1 = head1
        p2 = head2
        prev = head = None

        while p1 and p2:
            smaller = p1 if p1.val < p2.val else p2
            if not head:
                head = smaller
            if prev:
                prev.next = smaller
            prev = smaller

            if smaller == p1:
                p1 = p1.next
            else:
                p2 = p2.next

        if prev:
            prev.next = p1 or p2
        else:
            head = p1 or p2

        return head

    def merge_sort(head: LinkedList[int]) -> LinkedList[int]:
        if head and head.next:
            mid = middle(head)
            mid_next = mid.next
            # Makes it easier to stop
            mid.next = None

            return merge(merge_sort(head), merge_sort(mid_next))
        else:
            return head

    return merge_sort(linked_list)