Для задания я должен реализовать сортировку слиянием и вставкой в Python (этот код был нам передан) .
Однако затем мне нужно «провести эксперименты» с функцией timeit
, чтобы проверить время выполнения обоих алгоритмов, а затем составить график для определения их точки пересечения или когда вход пересекает порог, где слияние становится лучше, чем вставка (что-то указано в подсказке проблемы).
Вот мой код:
import random
import timeit
import array
# Insertion sort routine
def insertion_sort(A):
for k in range (1, len(A)): #from 1 to n-1
curr = A[k] #currently inserting element
j = k #find correct index j for current
while j > 0 and A[j - 1] > curr:
A[j] = A[j - 1]
j -= 1
A[j] = curr
# Merge sort routines
def merge(S1, S2, S):
i = j = 0
while i + j < len(S):
if j == len(S2) or (i < len(S1) and S1[i] < S2[j]):
S[i + j] = S1[i]
i += 1
else:
S[i + j] = S2[j]
j += 1
def merge_sort(S):
n = len(S)
if n < 2:
return
mid = n // 2
S1 = S[0:mid]
S2 = S[mid:n]
merge_sort(S1)
merge_sort(S2)
merge(S1, S2, S)
# Benchmark code
S = array.array('B',(0,)*300)
A = array.array('b', (0,)*300)
print(timeit.timeit("merge_sort(S)", setup = "from __main__ import merge_sort, S", number = 1))
print(timeit.timeit("insertion_sort(A)", setup = "from __main__ import insertion_sort, A", number = 1))
Для массива длиной 300. Независимо от размера, на который я изменяю свой массив, слияние всегда лучше, чем вставка.
Что мне здесь не хватает? Как я могу это исправить?