Source: Bisect - сортирвоанные списки

markdown source:
---
description: bisect в стандартной библиотеке python
tags: python-standart-library python
title: Bisect - сортирвоанные списки
---
Обеспечивает сортировку при вставке в список.

```python
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()` не имеет состояния и отбрасывает результаты функций после их использования. Следовательно, если функции поиска используются в цикле, функция может вызываться снова и снова для одних и тех же элементов массива.

[Документация](https://docs.python.org/3/library/bisect.html?highlight=bisect#module-bisect)

[[python-standart-library]]


[python-standart-library]: ../lists/python-standart-library "Стандартная библиотека python и полезные ресурсы"