最小掉期数对数组进行排序的正确性 [英] Correctness Of Minimum Number Of Swaps To Sort An Array
问题描述
问题来自这里： https：// www。 geeksforgeeks.org/minimum-number-swaps-required-sort-array/
我将在下面重复：
给定一个数组n
示例：
输入：{ 4，3，2，1}
输出：2
说明：将索引3与1和1与2与
交换，形成排序后的数组{1,2,3,4}。 / p>
输入：{1、5、4、3、2}
输出：2
I通过执行以下操作解决了该问题。
- 对数组进行排序（n log（n））时间
- 在比较排序数组和原始数组时，进行哈希处理以跟踪所需的交换。这应该是另一个O（n）时间
总时间复杂度应为：O（n +（n log n））= O （n log（n））
下面是我为此编写的代码，它适用于所提供的测试用例。
def解决方案（数组）
sorted = array.sort
puts array.inspect
puts sorted.inspect
counter_parts_that_have_been_seen = {}
number_of_swaps_required = 0
array.each_with_index做| val，idx |
如果counter_parts_that_have_been_seen [val] ==真
下一个
结束
array_val = val
sorted_val = sorted [idx]
如果array_val！= sorted_val
放置需要进行交换：array val为＃{array_val}，sorted_array_val为＃{sorted_val}
number_of_swaps_required + = 1
counter_parts_that_have_been_seen [sorted_val] = true
结束
结束
卖出需要的掉期数量为：＃{number_of_swaps_required}
$ b结束
现在，我的问题是，如何验证正确性？我不认为这种方法是正确的。
有人能对此有所了解吗？
索引：0 1 2 3 4 5 6 7 8 9
------ + ----- +- + --- + --- + --- + --- + --- + --- + --- +-
数组：1 22 32 42 12 83 64 93 73 53
------ + ----- + --- + --- + --- + --- + --- + --- + --- + --- +-
A BBBBBBBBBBBBBB CC DD CCCCCCCCCC
目标：0 2 3 4 1 8 6 9 7 5
差异：0 1 1 1 -3 3 0 2 -1 -4
来源：0 4 1 2 3 9 6 8 5 7
在此示例中，需要对array []进行排序。
- 目标位置是该位置在排序之后的索引
- 源位置是该位置此索引应从
中获取其值。
您可以看到四个（循环）组：
- A：1个成员
1 - B：4个成员
{22,32,42,12} - C：4个成员：
{83,93,73， 53} - D：1个成员：
64
已经对具有1个成员的组进行了排序：需要零交换。
具有4个成员的组可以按4个交换进行排序。 （最后一次交换将两个元素放到最终位置）
因此所需的交换次数为 0 + 3 + 3 + 0
现在，您只需要证明您可以在N-1个掉期中对N个循环进行分类...
The question is from here: https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/
I will repeat it below: Given an array of n distinct elements, find the minimum number of swaps required to sort the array.
Examples:
Input : {4, 3, 2, 1} Output : 2 Explanation : Swap index 0 with 3 and 1 with 2 to form the sorted array {1, 2, 3, 4}.
Input : {1, 5, 4, 3, 2} Output : 2
I have solved the problem by doing the following.
- Sorting the array (n log(n)) time
- Making a hash to keep track of the swaps required as I compare both the sorted array and the original array. This should be another O(n) time
Total Time Complexity should be: O(n + (n log n)) = O(n log(n))
Below is the code I have written for the same and it works for the test cases provided.
def solution(array)
sorted = array.sort
puts array.inspect
puts sorted.inspect
counter_parts_that_have_been_seen = {}
number_of_swaps_required = 0
array.each_with_index do | val, idx |
if counter_parts_that_have_been_seen[val] == true
next
end
array_val = val
sorted_val = sorted[idx]
if array_val != sorted_val
puts "A swap will be required: array val is #{array_val} and sorted_array_val is #{sorted_val}"
number_of_swaps_required += 1
counter_parts_that_have_been_seen[sorted_val] = true
end
end
puts "Number of swaps required are: #{number_of_swaps_required}"
end
Now, my question is, how does one verify the CORRECTNESS? I have no sense of weather this approach is correct.
Can anybody shed some light on this?
Index : 0 1 2 3 4 5 6 7 8 9
------+-----+---+---+---+---+---+---+---+---+--
Array : 1 22 32 42 12 83 64 93 73 53
------+-----+---+---+---+---+---+---+---+---+--
A BBBBBBBBBBBBBB CC DD CCCCCCCCCC
Target: 0 2 3 4 1 8 6 9 7 5
Diffs : 0 1 1 1 -3 3 0 2 -1 -4
Source: 0 4 1 2 3 9 6 8 5 7
In this example, the array[] needs to be sorted.
- Target is the index where this position should go after the sort
- source is the position where this index shoul get its value from
- diffs is the relative movement that the item at this index does during the sort
You can see four (cyclic) groups:
- A : 1 member
1 - B : 4 members
{22,32,42,12} - C : 4 members:
{83,93,73,53} - D : 1 member:
64
The groups with 1 member are already sorted: zero swaps needed. The groups with 4 members can be sorted with 4 swaps each. (the final swap puts two elements to their final place) So the number of swaps needed is 0+3+3+0
Now you only need to prove that you can sort an N-cycle in N-1 swaps...
这篇关于最小掉期数对数组进行排序的正确性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
