9 ТА_Поиск_Сортировка

1. Алгоритмы

Поиск и сортировка

2. Предварительные замечания

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

3. Оценки времени выполнения (бенчмарки)

import time
start_time = time.time()
# тестируемый код
end_time = time.time()
print(f" Время работы {end_time - start_time} секунд")

4. Алгоритмы поиска

5. Последовательный поиск в одномерном списке

Пусть есть список data и искомый элемент value.
Требуется найти, под каким номером этот элемент находится в списке.
Должны быть выведены номера ВСЕХ элементов списка, равных value.
Если таких элементов нет, ничего не выводится.
elem[0]=value?
elem[1]=value?
elem[2]=value?
...
elem[n]=value?
num = 0
for elem in data:
if elem == value:
print(num)
num+=1
Вычислительная сложность O(n)

6. Последовательный поиск в одномерном списке

Модификация
Требуется найти, под каким номером этот элемент находится в списке.
Должны быть выведены номера всех элементов списка, равных value.
Если таких элементов нет, выводится сообщение об этом.
elem[0]=value?
elem[1]=value?
elem[2]=value?
...
elem[n]=value?
found = False
num = 0
for elem in data:
if elem == value:
print(num)
found = True
num+=1
if (not found):
print("Ничего не найдено")
Вычислительная сложность O(n)

7. Последовательный поиск в одномерном списке

Модификация
Должен быть выведен номер одного (любого) элемента, равного value.
Если таких элементов нет, ничего не выводится.
elem[0]=value?
elem[1]=value?
elem[2]=value?
...
elem[n]=value?
num = 0
for elem in data:
if elem == value:
print(num)
break
num+=1
Вычислительная сложность O(n)
В худшем случае – n, в лучшем – const, в среднем – n/2.

8. Последовательный поиск в одномерном списке

Модификация
Должен быть выведен номер одного (любого) элемента, равного value.
Если таких элементов нет, выводится сообщение.
elem[0]=value?
elem[1]=value?
elem[2]=value?
...
elem[n]=value?
num = 0
for elem in data:
if elem == value:
print(num)
break
num+=1
else:
print("Ничего не найдено")
Вычислительная сложность O(n)
В худшем случае – n, в лучшем – const, в среднем – n/2.

9. Бинарный поиск

Должен быть выведен номер одного (любого) элемента, равного value.
Если таких элементов нет, ничего не выводится.
Важно! Работает только если список отсортирован в порядке возрастания
Бинарный поиск. Источник: brilliant.org

10. Бинарный поиск

Должен быть выведен номер одного (любого) элемента, равного value.
Если таких элементов нет, ничего не выводится.
Важно! Работает только если список отсортирован в порядке возрастания
elem[0]
Если да –
elem[1] ищем здесь
...
elem[n//2]>value?
...
Если нет –
ищем здесь
elem[n]
low = 0
high = len(data) - 1
while low < high:
mid = (low + high) // 2
if value > data[mid]:
low = mid + 1
else:
high = mid
if data[low] == value:
print("Есть под номером ",low)
else:
print("Нет такого")
Вычислительная сложность O(log2n)

11. Бинарный поиск

Модификация (продолжение)
Требуется найти, под каким номером искомый элемент находится в
списке.
Должны быть выведены номера ВСЕХ элементов списка, равных value.
num = low + 1
while num < len(data) and data[num] == value:
print("А еще ", num)
num += 1
Вычислительная сложность в худшем случае O(n)

12. Бинарный поиск

Предыдущий вариант – левый двоичный поиск, ищет минимальное
совпадение.
Модификация – правый двоичный поиск, ищет максимальное совпадение.
low = -1 # вместо 0
high = len(data) # убрано -1
while low < high - 1: # добавлено -1
#print(low, high)
mid = (low + high) // 2
if value >= data[mid]: # == заменено на >=
low = mid
else:
high = mid - 1 # добавлено -1
if data[low] == value:
print("Есть под номером ",low)
else:
print("Нет такого")
Вычислительная сложность O(log2n)

13. Бинарный поиск

Модификация – правый двоичный поиск, ищет максимальное совпадение.
Чтобы найти все элементы, совпадающие с искомым, надо двигаться к началу.
num = low - 1
while num < len(data) and
print("А еще ", num)
num -= 1
????
data[num]==value:
Вычислительная сложность в худшем случае O(n))

14. Бинарный поиск – когда выгодно?

Бинарный поиск требует отсортированных данных.
Сортировка (лучший метод) – O(n*log(n)).
Последовательный поиск – O(n)
Бинарный поиск – O(log(n)).
Если нужен однократный поиск – O(n*log(n))+ O(log(n)) – невыгодно!
Если нужно k поисков, критерий:
n*k >= n*log(n)+k*log(n)
Если верно неравенство – выгодно, если нет – невыгодно.

15. Бинарный поиск

Еще одна модификация
Требуется найти, под каким номером следует вставить новый элемент в
список, сохраняя возрастающий порядок элементов.
Должен быть возвращен номер позиции для нового элемента.
def insertValue(data, value):
low = -1
high = len(data)
while high > low + 1:
mid = (high + low) // 2
if value < data[mid]:
high = mid
else:
low = mid
return high
data.insert(insertValue(d,v),v)
# вставить элемент v в список d с сохранением порядка

16. Python: встроенные методы поиска

Метод index:
fruits = ["apple", "banana", "cherry", "elderberry", …]
index = fruits.index(fruit)
Работает на любом списке, при отсутствии выбросит исключение ValueError.
Как избежать?
1. Проверить наличие с помощью оператора in
if fruit in fruits:
index = fruits.index(fruit)
else:
index = None
2. Обработать исключение
try:
index = fruits.index(fruit)
except:
index = None

17. Алгоритмы сортировки

18. Сортировка одномерного списка: метод «пузырька»

Пусть есть список data и искомый элемент value.
Требуется упорядочить список по возрастанию.
Идея метода: просматриваем список, если два соседних элемента стоят
неверно – меняем их местами.
Выполняем просмотры, пока не убедимся, что список упорядочен
[5, 6, 2, 9, 4, 8]
[5, 2, 6, 4, 8, 9]
[2, 5, 4, 6, 8, 9]
[2, 4, 5, 6, 8, 9]
[2, 4, 5, 6, 8, 9]

19. Сортировка одномерного списка: метод «пузырька»

Пусть есть список data и искомый элемент value.
Требуется упорядочить список по возрастанию.
Идея метода: просматриваем список, если два соседних элемента стоят
неверно – меняем их местами.
Выполняем просмотры, пока не убедимся, что список упорядочен

20. Сортировка одномерного списка: метод «пузырька»

order = False
n = len(data)
while not order:
order = True
for i in range(n-1):
if data[i] > data[i+1]:
data[i],data[i+1] = data[i+1],data[i]
order = False
n -= 1
Вычислительная сложность
в худшем и среднем случае – O(n2),
в лучшем случае – O(n).

21. Сортировка одномерного массива: метод подсчета

Идея метода: создадим массив размера r – l+1,
где l – минимальный, а r – максимальный элемент массива.
После этого пройдем по массиву и подсчитаем количество вхождений
каждого элемента.
count_list = [0]*(r-l+2)
#нулевой элем не используем, но он есть
for elem in data:
count_list[elem] += 1
Вычислительная
сложность O(n)
for k in range(1,r-l+2):
за счет особенностей
for i in range(count_list[k]):
исходных данных!
f_out.write(str(k)+"\n")

22. Сортировка одномерного массива: метод подсчета

23. Метод Хоара (быстрая сортировка)

Идея метода:
• выберем некоторый элемент q, называемый барьерным
элементом
• разобьем массив на две части, переупорядочив его элементы;
в первой части соберем элементы, меньшие или равные q,
а во второй части — большие или равные q
• теперь достаточно отсортировать обе части, после чего
выполнить их конкатенацию

24. Метод Хоара (быстрая сортировка)

Вычислительная сложность зависит от метода выбора барьерного элемента.
В лучшем случае O(n·log2n), в худшем – O(n2)
В идеале должен выбираться медианный элемент массива
(т.е. такое число, что половина элементов массива имеют большее значение, а
половина — меньшее),
но его поиск нельзя выполнить быстро.
Как правило выбирается случайный элемент списка. Тогда алгоритм
становится вероятностным — время его работы зависит от того, каким будет
случайно выбранный элемент.
В теории вероятностей доказывается, что средняя сложность алгоритма
быстрой сортировки Хоара — O(n·log2n).

25. Метод Хоара (быстрая сортировка)

def QuickSort(A, l, r):
if l >= r:
return
else:
q = random.choice(A[l:r + 1])
i = l
j = r
while i <= j:
while A[i] < q:
i += 1
while A[j] > q:
j -= 1
if i <= j:
A[i], A[j] = A[j], A[i]
i += 1
j -= 1
QuickSort(A, l, j)
QuickSort(A, i, r)
QuickSort(data,0,len(data)-1)

26. Устойчивость сортировки

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

27. Python: встроенные методы сортировки

1. Метод sort – сортировка «на месте», не возвращает значения
A = [random.randint(1, 1000) for i in range(1000)]
A.sort()
2. Функция sorted – не модифицирует переданный ей список, а возвращает новый.
A = [random.randint(1, 1000) for i in range(1000)]
B = sorted(A)
Можно использовать в вводе-выводе.
Такая программа сортирует считанный со стандартного ввода список, состоящий из
чисел, разделенных пробелами, и выводит результат на экран.
print(" ".join(map(str, sorted(map(int, input().split())))))
И методу sort, и функции sorted можно передать дополнительный параметр reverse,
reverse =True означает сортировку в обратном порядке.

28. Python: встроенные методы сортировки

Сортировать можно списки любых объектов, которые допускают
сравнения — чисел, строк (сравниваются лексикографически),
кортежей.
Можно объявить собственный класс объектов, определить для них
функцию сравнения, тогда встроенная сортировка сможет их
сортировать.
В языке Питон есть встроенный алгоритм сортировки — Timsort.
На больших списках он работает, как сортировка слиянием, а на
маленьких фрагментах — как сортировка вставками. Этот алгоритм
специально оптимизирован для использования в языке Питон, а также
быстро работает (за линейное время), если исходный список почти
отсортирован.

29. Полезные ссылки

• https://habr.com/ru/post/335920/
• https://tproger.ru/translations/sorting-for-beginners/
• https://foxford.ru/wiki/informatika/bystraya-sortirovka-hoara-python

30.

Лекция окончена
Спасибо за внимание
☺