Нитевидная сортировка :: Strand sort

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

Нитевидная сортировка

Алгоритм

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

Временная сложность

Достаточно скромна — в среднем O(n2). Однако весьма эффективна при работе с почти упорядоченными списками — O(n).

Характеристики алгоритма

Название Нитевидная сортировка (Strand sort)
Класс Сортировки слиянием
Устойчивость Да
Сравнения Да
Сложность по времени Худшая O(n2)
Средняя O(n2)
Лучшая O(n)
Сложность по памяти Общая O(n)

Ссылки

Strand sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий