Неделя 3 — Алгоритмы и сложность

Примеры кода

1. Линейный поиск:
```python
def linear_search(arr, target):
for i in range(len(arr)):
    if arr[i] == target:
        return i
return -1
```

2. Бинарный поиск:
```python
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
return -1
```

3. Пузырьковая сортировка:
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
    for j in range(0, n - i - 1):
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
```

Практические упражнения

1. Реализуйте линейный поиск и протестируйте его на списке из 10 чисел.
2. Напишите бинарный поиск и сравните скорость его работы с линейным.
3. Реализуйте пузырьковую сортировку и отсортируйте список случайных чисел.
4. Реализуйте сортировку выбором.

Задания на самостоятельную работу

1. Напишите программу, которая определяет, отсортирован ли список.
2. Реализуйте сортировку вставками и сравните её с пузырьковой.
3. Напишите функцию, которая возвращает количество сравнений при сортировке.
4. Попробуйте отсортировать список строк по длине.

Контрольные вопросы

1. В чём разница между линейным и бинарным поиском?
2. Почему бинарный поиск требует отсортированного массива?
3. Какая асимптотическая сложность у пузырьковой сортировки?
4. Что означает Big O и зачем она используется?
5. Почему важно выбирать эффективные алгоритмы?