Решаем задачи Python

right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

# Функция для замера времени выполнения

def measure_time(sort_function, arr):

start_time = time.time()

sorted_arr = sort_function(arr)

end_time = time.time()

return sorted_arr, end_time – start_time

# Генерация случайного списка для сортировки

arr = [random.randint(0, 1000) for _ in range(1000)]

# Сравнение производительности с собственной и встроенной сортировкой

sorted_arr_custom, time_custom = measure_time(quick_sort, arr)

sorted_arr_builtin, time_builtin = measure_time(sorted, arr)

print("Время выполнения собственной сортировки:", time_custom)

print("Время выполнения встроенной сортировки:", time_builtin)

```

Объяснения к коду:

– `quick_sort`: Это наша реализация алгоритма быстрой сортировки. Он разбивает массив на подмассивы вокруг опорного элемента, рекурсивно сортируя каждую подгруппу, а затем объединяет их в один отсортированный массив.

– `measure_time`: Это функция, которая принимает на вход функцию сортировки и список для сортировки, замеряет время выполнения этой функции над списком и возвращает отсортированный список и время выполнения.

– Мы генерируем случайный список `arr` для сортировки.

– Затем мы вызываем `measure_time` для нашей собственной реализации быстрой сортировки и для встроенной функции сортировки Python (`sorted()`).

– Наконец, мы выводим время выполнения каждой из функций сортировки для сравнения.

9. Задача о рекурсии: Реализовать алгоритм бинарного поиска с использованием рекурсии.

Идея решения:

Алгоритм бинарного поиска используется для поиска элемента в отсортированном массиве. Он работает путем разделения массива на две части и сравнения искомого элемента с элементом в середине массива. Если элемент найден, возвращается его индекс. Если элемент не найден, алгоритм рекурсивно вызывается для подмассива, который должен содержать искомый элемент.

Код:

```python

def binary_search_recursive(arr, target, left, right):

if left > right:

return -1

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

return binary_search_recursive(arr, target, mid + 1, right)

else:

return binary_search_recursive(arr, target, left, mid – 1)

# Пример использования:

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]

target = 11

index = binary_search_recursive(arr, target, 0, len(arr) – 1)

if index != -1:

print(f"Элемент {target} найден в позиции {index}.")

else:

print(f"Элемент {target} не найден.")

```

Объяснения к коду:

– Функция `binary_search_recursive` принимает отсортированный массив `arr`, искомый элемент `target`, левую границу `left` и правую границу `right`.

– Если `left` больше `right`, значит, искомый элемент не найден, поэтому функция возвращает `-1`.

– Иначе, находим индекс `mid` элемента в середине отрезка между `left` и `right`.