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`.
– Если значение в `arr[mid]` равно `target`, возвращаем `mid`.
– Если `arr[mid]` меньше `target`, рекурсивно вызываем функцию для правой половины массива, начиная с `mid + 1`.