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

Question

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

Answer 1

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

Тем не менее, интересно узнать, можете ли вы отсортировать его по номеру in-place, stably, его худшем случае и так далее.

Саймон Татхам, известность Шпаклера, объясняет, как sort a linked list with merge sort. Он заключает следующие замечания:

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

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

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

Как @ Йорген Фог упоминает ниже, большой-O обозначение может скрыть некоторые постоянные факторы, которые могут вызвать один алгоритм для выполнения лучше из-за локальность памяти, из-за низкое количество элементов и т.п.

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

Другим классом специальных данных является сортировка сортированного списка почти отсортированного списка с отсутствием порядка элементов. Это можно отсортировать в операциях 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); 
} 

Answer 6

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

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

Answer 7

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

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

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

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

--- EDIT

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

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

N = 1000:

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

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

Упакованного список с сортировкой слияния : 0,000000 секунд

N = 100000:

Fragmented список с сортировкой слияния: 0.039000 секунд

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

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

N = 1000000 :

Фрагментированный список с сортировкой слияния: 1.162000 secon ds

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

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

N = 100000000:

Fragmented список с сортировкой слияния: 364.797000 секунд

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

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

Вывод:

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

Answer 8

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

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

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

Answer 9

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

Answer 10

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

СРАВНИТЕЛЬНОЕ ИЗУЧЕНИЕ СВЯЗАННЫХ СПИСКА SORTING АЛГОРИТМОВ по Чинг-Куанг Шене

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

Answer 11

Here's an implementation что проходит список только один раз, собирая пробегов, то графики, слияния таким же образом, что сортировка слиянием делает.

Сложность - это 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); 
    } 

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

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

Или просто посмотреть википедии на bottom-up mergesort.