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

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

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

Однако интересная часть состоит в том, чтобы исследовать, можете ли вы сортировать ее на месте , стабильно , в худшем случае и так далее.

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

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

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

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

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

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

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

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

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

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

Я решил проверить свою гипотезу и написал C-программу, которая измеряет время (используя clock() ), которое требуется для сортировки связанного списка int. Я попробовал со связанным списком, где каждому узлу был назначен malloc() и связанный список, где узлы были выложены линейно в массиве, поэтому производительность кэша была бы лучше. Я сравнивал их со встроенным qsort, который включал копирование всего из fragmentированного списка в массив и копирование результата обратно. Каждый алгоритм выполнялся на тех же 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 ГГц Phenom II, но только 0,6 ГГц 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). Например, если вы работаете с целыми числами не больше некоторого значения, вы можете использовать Counting Sort или Radix Sort , так как они используют определенные объекты, которые вы сортируете, чтобы уменьшить сложность с долей n. Будьте осторожны, однако, они добавляют некоторые другие вещи к сложности, которую вы не можете учитывать (например, подсчет сортировки и сортировка Radix добавляют как факторы, основанные на размере сортируемых чисел, O (n + k ), где k – размер наибольшего числа для Counting Sort, например).

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

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

СРАВНИТЕЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ СОРТИРОВАННОГО СПИСКА ЧИНГ-КУАН ШЕН

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

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

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

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

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

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

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

 #include  #include  #include  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 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) ] [ () (ad) ] [ (g), (ad) ] [ () () (adgi) ] [ (b) () (adgi) ] [ () (be) (adgi) ] [ (c) (be) (adgi ) ] [ () () () (abcdefgi) ] [ (j) () () (abcdefgi) ] [ () (hj) () (abcdefgi) ] 

Затем, наконец, слейте все эти списки.

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

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

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

Или просто посмотрите wikipedia на восходящем слиянии .

  • Простой вид пузыря c #
  • Сортировка ObservableCollection C #
  • Как сортировать быстрый массив, содержащий экземпляры подclassа NSManagedObject, по значению атрибута (date)
  • Какой тип использует Java Collections.sort (узлы)?
  • Лучший способ рандомизировать массив с .NET.
  • c ++ сортировка, отслеживающая индексы
  • Как отсортировать массив объектов в Java?
  • Самый быстрый тип фиксированной длины 6 int array
  • Как отсортировать список словарей по значению словаря в Python?
  • Как отсортировать вектор символа, где элементы содержат буквы и числа в R?
  • Что такое стабильность в алгоритмах сортировки и почему это важно?
  • Interesting Posts

    Последовательный портовый опрос и обработка данных

    Сериализация данных частного участника

    Быстрый способ adduser и userdel на нескольких машинах

    Почему я получаю «алгоритм не сходился» и «устанавливал prob численно 0 или 1» предупреждения с помощью glm?

    Поддерживать соотношение сторон по ширине и высоте

    Как сделать 2 сопоставимых метода только в одном classе?

    Невозможно ввести какой-либо специальный символ или umlaut в терминале

    Поиск в ArrayList с пользовательскими объектами для определенных строк

    Как добавить и синхронизировать папки за пределами папки SkyDrive?

    SFINAE работает в обратном типе, но не как параметр шаблона

    Как сделать аутентификацию без учета состояния (без сеанса) и без cookie?

    Что более эффективно: вернуть значение против Pass by reference?

    Возможно ли в Matlab явно форматировать выходные номера?

    Что означает «статическое» значение в C?

    Альтернатива предпочтениям на Java

    Давайте будем гением компьютера.