最小交换次数排序

在本教程中，我们将编写 Python 程序来查找排序给定列表所需的最小交换次数。我们给出了一个包含 n 个不同元素的数组，我们需要找到将数组按升序排序所需的最小交换次数。例如 -

示例 1

输入

nums = [2, 8, 5, 4]

输出

1

说明

将 8 与 4 交换。

示例 2

输入

nums = [10, 19, 6, 3, 5]

输出

2

说明

将 10 与 3 交换，将 19 与 5 交换。

让我们来实现上述问题的解决方案。

解决方案 -

让我们从视觉上理解上述问题。我们将有 n 个节点，如果第 i 个索引处的元素必须存在于排序数组的第 j 个索引处，则从节点 i 到节点 j 有一条有向边。下面是输入图。

正如我们所见，需要两次交换才能使数组按升序排序。我们需要识别给定数组中的循环。让我们来理解下面的例子。

示例 -

输出

Minimum Swap Required:  2

解释 -

在上面的代码中，我们首先创建一个接受列表作为参数的 **minimum_swaps()** 函数。然后我们初始化 swaps 变量，它将跟踪执行的交换次数。然后我们复制数组到 **arr_copy**，以便我们可以执行交换而不更改原始数组。然后，我们对复制的数组进行排序以获得预期的输出。我们创建了一个大小为 n、值为 **False** 的 visited 数组来跟踪已访问的元素。然后我们迭代数组的每个元素并执行以下步骤 -

a. 检查当前元素是否已被访问，或者它是否在其正确排序的位置（即当前索引等于元素值减一）。

如果为真，则继续下一个元素。

如果为假，则表示我们遇到了一个新的循环。初始化一个名为 cycleSize 的变量为 0，它将表示当前循环的大小。

进入循环直到我们完成循环

i. 将当前元素标记为已访问。

ii. 递增 cycleSize 变量。

iii. 更新当前元素到其正确的排序位置。

iv. 如果新元素与原始元素相同，则退出循环，因为循环已完成。

退出循环后，将 cycleSize - 1 添加到 swaps 变量。这是因为大小为 cycleSize 的循环需要 cycleSize - 1 次交换才能排序。

然后我们返回 swaps 的值。

我们可以在不创建数组副本和对其进行排序的情况下解决它。我们可以假设给定的数组包含不同的元素，并利用循环检测概念来找到所需的最小交换次数。

让我们理解下面的例子。

示例 -

输出

2

解释 -

在上面的代码中，我们实现了一个名为 **minimum_swaps()** 的函数，该函数计算将数组 arr 排序为升序所需的最小交换次数。它使用了选择排序算法的修改版本。

**minimum_swaps()** 函数接受一个数组 arr 作为输入。它初始化两个变量：n 为数组 arr 的长度，swaps 为一个计数器，用于跟踪执行的交换次数。然后我们使用一个 for 循环，该循环从 0 迭代到 n-1，代表数组中元素的索引。

在循环中，它检查当前元素 arr[i] 是否在其正确的排序位置，即 i + 1（因为数组预计包含从 1 开始的连续数字）。

如果元素不在其正确的位置，它将进入一个 while 循环，直到元素被交换到其正确的位置。

在 while 循环内部，代码执行交换操作。它将当前元素临时存储在变量 temp 中，然后通过访问 arr[temp - 1] 将当前元素与其正确位置的元素进行交换。使用 -1 是因为数组索引从 0 开始。

交换后，计数器 swaps 增加 1。

while 循环一直持续到当前元素处于正确位置，然后代码继续执行 for 循环的下一个迭代。

for 循环完成后，函数返回执行的总交换次数。

最后，我们传入一个包含元素 [4, 3, 1, 2] 的数组 arr，并使用此数组作为参数调用 minimum_swaps 函数。结果存储在 result 变量中。

最后，打印结果的值，它表示对数组进行排序所需的最小交换次数。在这种情况下，输出将是 2。