Bisect - сортирвоанные списки
Обеспечивает сортировку при вставке в список.
import bisect
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]
l = []
for i in values:
position = bisect.bisect(l, i)
bisect.insort(l, i)
print('{:3} {:3}'.format(i, position), l)
>>> 14 0 [14]
>>> 85 1 [14, 85]
>>> 77 1 [14, 77, 85]
>>> 26 1 [14, 26, 77, 85]
>>> 50 2 [14, 26, 50, 77, 85]
>>> 45 2 [14, 26, 45, 50, 77, 85]
>>> 66 4 [14, 26, 45, 50, 66, 77, 85]
>>> 79 6 [14, 26, 45, 50, 66, 77, 79, 85]
>>> 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
>>> 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
>>> 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
>>> 77 8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
>>> 1 0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
Алгоритм по разному обрабатывает повторяющиеся значения - они вставляются либо слева от имеющегося либо справа. insort() эквивалентен вставке слева. См. документацию для изменеения поведения.
Bisect эффективен для поиска диапазонов значений. Для поиска определенных значений словари более эффективны.
Сложность insort() - O(n), потому что на этапе логарифмического поиска преобладает этап вставки с линейным временем.
insort() не имеет состояния и отбрасывает результаты функций после их использования. Следовательно, если функции поиска используются в цикле, функция может вызываться снова и снова для одних и тех же элементов массива.