```
Этот код работает аналогично предыдущему, но мы добавил функцию `evaluate_reverse_polish_notation`, которая принимает строку в обратной польской записи и возвращает результат вычислений. Каждый токен выражения разделяется пробелами при помощи метода `split()`, чтобы создать список токенов. Затем итерируется по этому списку. Если текущий токен является числом, он добавляется в стек. Если текущий токен – оператор, извлекаются два операнда из стека, выполняется операция и результат помещается обратно в стек. После завершения итераций в стеке остается только один элемент – результат вычислений, который возвращается из функции.
8. Задача о сортировке: Реализовать свой алгоритм сортировки и сравнить его производительность с встроенной функцией сортировки Python.
Идея решения:
Для реализации собственного алгоритма сортировки, мы можем использовать один из классических алгоритмов, таких как сортировка пузырьком, сортировка вставками, сортировка выбором или быстрая сортировка. Давайте выберем быструю сортировку (Quick Sort) из-за ее высокой производительности в среднем случае.
Идея быстрой сортировки заключается в следующем:
1. Выбирается опорный элемент из массива.
2. Массив разделяется на две подгруппы: одна содержит элементы, меньшие опорного, а другая – большие.
3. Рекурсивно применяется алгоритм к каждой подгруппе.
Для сравнения производительности нашего алгоритма сортировки с встроенной функцией сортировки Python (например, `sorted()`), мы можем измерить время выполнения каждого метода на одних и тех же данных.
Код:
```python
import time
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
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)