比较排序算法

Question

我正在尝试比较一些排序算法，我想同时运行它们并获得排序、交换和比较的时间。 我有这两种算法：

def bubble_sort(nums):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                swapped = True


def selection_sort(nums):
    for i in range(len(nums)):
        lowest_value_index = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[lowest_value_index]:
                lowest_value_index = j
        nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]
        return nums

我想运行它们，对 10、100 和 1000 个整数的列表进行排序，每个整数 10 次。因此，我希望有平均时间来处理、交换和比较这两种算法。

ten_ = np.random.randint(0, 10000, size=10)
hundred_ = np.random.randint(0, 10000, size=100)
thous_ = np.random.randint(0, 10000, size=1000)


sort_algorithms = (
        bubble_sort,
        selection_sort)

for algo in sort_algotithms:

我在这里迷失了：我想对 ten_、 Hundred_、thous_ 列表进行排序以获取指标：时间、交换、比较

有人可以帮我吗？

Answer 1

首先，要为函数计时，您可以使用

time

库

import time

start_time = time.time()
bubble_sort(ten_)
end_time = time.time() - start_time

没有简单的技巧来计算比较和交换的次数：您必须在函数中添加一些代码来计算它们。例如：

def bubble_sort(nums):
    swapped = True
    compares = 0
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            compares += 1
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                swapped = True

    return nums, compares

此外，当您将可变对象（例如列表、字典、numpy 数组）传递给函数时，您需要注意。您的函数将修改函数外部的变量。例如：

print(ten_)
bubble_sort(ten_)
print(ten_)

打印函数为同一变量返回不同的值，即使您没有显式更改它。为了避免这种情况，请在函数的开头添加一行

nums = nums.copy()

Answer 2

你可以这样做：

from time import perf_counter
import numpy as np


def bubble_sort(nums):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                swapped = True


def selection_sort(nums):
    for i in range(len(nums)):
        lowest_value_index = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[lowest_value_index]:
                lowest_value_index = j
        nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]
        return nums


ten_ = np.random.randint(0, 10000, size=10)
hundred_ = np.random.randint(0, 10000, size=100)
thous_ = np.random.randint(0, 10000, size=1000)

sort_algorithms = (
    bubble_sort,
    selection_sort)

for algo in sort_algorithms:
    start_time = perf_counter()
    thous_ = thous_.copy()
    algo(thous_)
    end_time = perf_counter() - start_time
    print(f'{algo.__name__}() took {end_time:.3f} seconds to execute')
    print()