Нахождение точки пересечения для сортировки слиянием и выделением в Python - PullRequest
0 голосов
/ 29 октября 2018

Для задания я должен реализовать сортировку слиянием и вставкой в ​​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. Независимо от размера, на который я изменяю свой массив, слияние всегда лучше, чем вставка.

Что мне здесь не хватает? Как я могу это исправить?

...