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

Question

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

下面是我的代码。该代码毫无问题地解决了列表，但时间和交换计数器无法正常工作，它只给我 0,1,1,1,2,1,1,0,2,4 之类的结果。

我在添加计数时做错了什么，在 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之前启动定时器，并在函数调用期间检查时间。

Answer 2

扩展我的评论：因为你递归调用 mergeSort，你需要用另一个函数包装它来测量开始和结束时间。

然后，为了正确跟踪交换次数，因为 mergeSort 就地改变数组，您可以使用 return 到 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)

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

Array Merge sort Sorting Count and Sorting time Python

python

arrays

sorting

mergesort