Помогите пожалуйста, срочно нужно по Python написать код. Отдам 40 баллов.
1. Реализовать алгоритм сортировки слиянием.
Он должен заключаться в разделении исходного массива на две равные половины, сортировке каждой из половин и последующем их слиянии в отсортированный массив.
!!! запрещено использовать стандартные функции сортировки в python.
2. Дан упорядоченный по возрастанию массив с числами, требуется сгенерировать все его перестановки. Перестановка n объектов/элементов — это способ их последовательного расположения с учётом порядка. Например: abc, bca и cab — это разные перестановки трёх букв.
Решите задачу итерационно и рекурсивно. Опишите, какой подход лучше и почему.
Ответы
1. Реализация сортировки слиянием
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
Этот алгоритм работает следующим образом:
Если массив имеет один элемент, то он уже отсортирован.
В противном случае, массив делится пополам, и каждая половина сортируется рекурсивно.
Затем две отсортированные половины объединяются в один отсортированный массив.
2. Решение задачи итеративно и рекурсивно
Итеративный подход
def permutations(arr):
if len(arr) <= 1:
return [arr]
permutations_without_first = permutations(arr[1:])
result = []
for permutation in permutations_without_first:
for i in range(len(permutation) + 1):
new_permutation = permutation[:i] + [arr[0]] + permutation[i:]
result.append(new_permutation)
return result
Этот алгоритм работает следующим образом:
Для каждой позиции в массиве, кроме первой, добавляется эта позиция в начало всех возможных перестановок без нее.
Рекурсивный подход
def permutations_recursive(arr):
if len(arr) <= 1:
return [arr]
permutations_without_first = permutations_recursive(arr[1:])
result = []
for permutation in permutations_without_first:
for i in range(len(permutation) + 1):
new_permutation = permutation[:i] + [arr[0]] + permutation[i:]
result.append(new_permutation)
return result
Этот алгоритм работает следующим образом:
Рекурсивно вызывает себя для массива без первой позиции.
Для каждой позиции в массиве, кроме первой, добавляется эта позиция в начало всех возможных перестановок массива без нее.
Сравнение подходов
Итеративный подход имеет ряд преимуществ перед рекурсивным:
Он более эффективный, так как не требует использования стека.
Он проще в понимании и реализации.
Рекурсивный подход имеет следующие преимущества:
Он более компактный.
Он более гибкий, так как может быть использован для решения более общих задач.
В данном случае итеративного подхода предпочтительнее, так как он более эффективный и простой.