Эффективная реализация сортировки слиянием в Python
def merge(arr, l, m, r):
merged_arr = []
i, j = 0, 0
while (i < len(arr[l:m])) and (j < len(arr[m:r+1])):
if arr[l+i] < arr[m+j]:
merged_arr.append(arr[l+i])
i += 1
elif arr[l+i] >= arr[m+j]:
merged_arr.append(arr[m+j])
j += 1
merged_arr.extend(arr[m+j:r+1])
merged_arr.extend(arr[l+i:m])
arr[l:r+1] = merged_arr
return
def merge_sort(arr, l, r):
if r > l:
m = (l + r) // 2
merge_sort(arr, l, m)
merge_sort(arr, m+1, r)
return merge(arr, l, m, r)
Я не уверен, что не так с моей функцией merge. Хорошо работает следующее:
print(merge([1,4,7,8,9,20, 0,4,5,15,67,68], 0, 6,12))
Однако это не дает правильного вывода:
print(merge_sort([1, 5, 4, 2, 33, 4, 2, 44, 22, 0], 0, 10))
Проследите его: сначала найдите «какой-то короткий список», который терпит неудачу, например, просто [1,5,4], а затем пройдитесь по коду, используя операторы печати, если нужно: в какой момент то, что, по вашему мнению, должно произойти, перестанет происходить? Кроме того, в более общем плане, вы хотите, чтобы merge_sort либо просто брал массив и выдавал результат, либо чтобы эти аргументы l и r по умолчанию имели какое-то значение (например, (arr, l=0, r=len(arr))), и добавляли оператор возврата, когда r не больше, чем l.
Спасибо за ваш комментарий. Я это сделал. Каким-то образом, если я заменю все вхождения m на m+1 в функции merge(...), это сработает. Но я не могу понять, почему это должно иметь значение.
Ответы 1
Конечный индекс для нарезки не включает:
def merge(arr, l, m, r):
L, R, i, j = arr[l:m], arr[m:r], 0, 0
merged_arr = []
while i < len(L) and j < len(R):
if L[i] < R[j]:
merged_arr.append(L[i])
i += 1
else:
merged_arr.append(R[j])
j += 1
merged_arr.extend(L[i:])
merged_arr.extend(R[j:])
arr[l:r] = merged_arr
def merge_sort(arr, l, r):
if r - l > 1:
m = (l + r) // 2
merge_sort(arr, l, m)
merge_sort(arr, m, r)
merge(arr, l, m, r)
A = [1, 5, 4, 2, 33, 4, 2, 44, 22, 0]
merge_sort(A, 0, len(A))
print(A)
Принты
[0, 1, 2, 2, 4, 4, 5, 22, 33, 44]
У нас есть инвариант, который
l < r. Какие еще инварианты вы можете записать, например как связаныlиm? Как связаныmиr? Добавьте операторыassertв свой код и покажите нам результат.