使用选择排序对python中的数组进行排序.我该如何优化? [英] Using a selection sort to sort an array in python. How can I optimize?

问题描述

在HackerRank上进行此挑战，并将此代码通过15个测试用例中的10个.由于超时错误而失败，这是HackerRank告诉您算法未优化的方式.如何优化此代码以在较大的输入数据上运行?

Working on this challenge on HackerRank and got this code to pass 10 out of 15 test cases. It is failing due to timeout error which is HackerRank's way of telling you that the algorithm is not optimized. How can I optimize this code to run on larger input data?

目标是找出对未排序数组进行排序所需的最小交换次数.

The goal is to figure out the minimum number of swaps necessary to sort an unsorted array.

更新:数组中的每个元素都是不同的.

Update: Each element in the array is distinct.

def minimum_swaps(arr):
"""Returns the minimum number of swaps to re-oder array in ascending order."""

    swaps = 0
    for val in range(len(arr) - 1, 0, -1):

        # Index of max value
        max_pos = 0
        for index in range(1, val + 1):

            if arr[index] > arr[max_pos]:
                max_pos = index

        # Skip if value is already in sorted position
        if max_pos == val:
            continue

        arr[val], arr[max_pos] = arr[max_pos], arr[val]
        swaps += 1

    return swaps

推荐答案

查看代码.它具有2个嵌套循环:

Look at the code. It has 2 nested loops:

• 外部循环在位置val上迭代.
• 内部循环找到应该在索引val处的值的索引，即max_pos.

• The outer loop iterates over the positions val.
• The inner loop finds the index of the value that should be at the index val, i.e., max_pos.

仅花费大量时间才能找到索引.相反，我将计算每个值的索引并将其存储在dict中.

It takes a lot of time just to find the index. Instead, I will compute the index of each value and store it in a dict.

index_of = {value: index for index, value in enumerate(arr)}

(请注意，由于arr中的所有值都是不同的，因此不应有重复的键)

(note that because all values in arr are distinct, there should be no duplicated keys)

还要准备一个数组的排序版本:这样一来，找到最大值就更容易了，而不必遍历数组.

And also prepare a sorted version of the array: that way it's easier to find the maximum value instead of having to loop over the array.

sorted_arr = sorted(arr)

然后执行其余操作，类似于原始代码:对于每个访问的索引，使用sorted_arr获取最大值，使用index_of获取其当前索引，如果它不在原位，则进行交换.记住也要在交换时更新index_of字典.

Then do the rest similar to the original code: for each index visited, use sorted_arr to get the max, use index_of to get its current index, if it's out-of-place then swap. Remember to update the index_of dict while swapping too.

该算法需要进行O(n)个操作(包括dict索引/修改)，再加上n个元素的排序成本(大约为O(n log n)).

The algorithm takes O(n) operations (including dict indexing/modifying), plus sorting cost of n elements (which is about O(n log n)).

注意:如果数组arr仅包含较小范围内的整数，则将index_of设置为数组而不是dict可能会更快.

Note: If the array arr only contains integers in a small range, it may be faster to make index_of an array instead of a dict.

这篇关于使用选择排序对python中的数组进行排序.我该如何优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！