数组合并排序排序计数和排序时间Python

Question

我已经创建了一个程序，其中为列表/数组随机生成数字。在此列表中，我需要计算对列表进行排序所需的时间以及排序所需的交换数量。

下面是我的代码。代码解决了列表没有任何问题，但时间和交换计数器没有正常工作，它只给我0,1,1,1,2,1,1,0,2,4喜欢的结果。

在对count和start.time和end.time进行加法运算时，我是否做错了什么

import random
import time
#X--------------------------------------------------------------------------------------------------------------------------------------------------------------------

# Random Number Generator
def random_generator():
    randomNumber = random.randint(0, 1000)
    return randomNumber
#X--------------------------------------------------------------------------------------------------------------------------------------------------------------------

def arraygenerator():
    arr = []
    for draw in range(8):
        randomNumber = random_generator()
        arr.append(randomNumber)
    print ("Unsorted Array is : ", arr)
    return arr
#X--------------------------------------------------------------------------------------------------------------------------------------------------------------------
#Insertion Sort
def mergeSort(A):
    

    b = 0
    start = time.time() # Start Timmer
    if len(A) > 1:
 
         # Finding the mid of the array
            mid = len(A)//2
 
        # Dividing the array elements
            L = A[:mid]
 
        # into 2 halves
            R = A[mid:]
 
        # Sorting the first half
            mergeSort(L)
 
        # Sorting the second half
            mergeSort(R)
 
            i = j = k = 0
            
 
        # Copy data to temp arrays L[] and R[]
            while i < len(L) and j < len(R):
                if L[i] < R[j]:
                    A[k] = L[i]
                    i += 1
                    
                else:
                    A[k] = R[j]
                    j += 1
                k += 1
                b = b+1
 
        # Checking if any element was left
            while i < len(L):
                A[k] = L[i]
                i += 1
                k += 1
                
 
            while j < len(R):
                A[k] = R[j]
                j += 1
                k += 1
 
    end = time.time() # End Timmer
    printf(end, start, b)
    
    
      

def printf(end, start, b):
    
    print(f"Runtime of the program is {end - start}")
    print ("Total Number of Swaps : ", b)
    

A = arraygenerator()

mergeSort(A)
print ("Sorted array", A)

Unsorted Array is :  [684, 508, 361, 743, 745, 353, 521, 55]
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.031590938568115234
Total Number of Swaps :  1
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.02653813362121582
Total Number of Swaps :  1
Runtime of the program is 0.08834385871887207
Total Number of Swaps :  3
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.023435115814208984
Total Number of Swaps :  1
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.0
Total Number of Swaps :  0
Runtime of the program is 0.024811744689941406
Total Number of Swaps :  1
Runtime of the program is 0.07755494117736816
Total Number of Swaps :  3
Runtime of the program is 0.1909334659576416
Total Number of Swaps :  7
Sorted array [55, 353, 361, 508, 521, 684, 743, 745]

Answer 1

展开我的评论:由于您以递归方式调用mergeSort，因此需要用另一个函数对其进行包装，以测量开始和结束时间。

然后，为了正确跟踪交换的数量，因为mergeSort就地改变了数组，所以您可以使用return返回由该mergeSort调用(可能是内部的、递归的)进行的交换的数量：

import random
import time


def _merge_sort(A):
    swaps = 0
    if len(A) > 1:

        # Finding the mid of the array
        mid = len(A) // 2

        # Dividing the array elements
        L = A[:mid]

        # into 2 halves
        R = A[mid:]

        # Sorting the first half
        swaps += _merge_sort(L)

        # Sorting the second half
        swaps += _merge_sort(R)

        i = j = k = 0

        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                A[k] = L[i]
                i += 1

            else:
                A[k] = R[j]
                j += 1
            k += 1
            swaps += 1

        # Checking if any element was left
        while i < len(L):
            A[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            A[k] = R[j]
            j += 1
            k += 1

    return swaps


def mergeSort(A):
    start = time.time()  # Start Timmer
    swaps = _merge_sort(A)
    end = time.time()  # End Timmer
    print(f"Runtime of the program is {end - start}")
    print("Total Number of Swaps : ", swaps)


A = [random.randint(0, 1000) for x in range(8)]
print("Unsorted array", A)
mergeSort(A)
print("Sorted array", A)

Answer 2

您编写它的方式是让计时器在每次mergeSort函数调用时调用。如果您想要程序的真实运行时，请在调用mergeSort之前启动计时器，并在函数调用期间检查时间。