Correctness Of Minimum Number Of Swaps To Sort An

问题:

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.

1. Sorting the array (n log(n)) time
2. 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?

回答1:

Starting at the first element in the unsorted array, check if it is in the correct place, if not swap the correct value into that position. The test can either be done as you did by comparing to a sorted version of the collection, or the selected element can be compared to each element that follows it.

As you go along you may encounter elements that are in the correct position - either because they started in the correct place or they were swapped there when placing an earlier element (the last element must be by the time all other ones have been placed). Just leave those in place and move to the next element.

With this method every swap places at least one element correctly, some swaps will correctly place both.

An element in a correct place can be discounted from the problem - there is never a need to move it from its correct place to sort any other elements. Also a pair of elements that in each others places (e.g. 3 and 1 in {3,2,1} ) never need to be swapped with any of the other elements. They form their own independent set of elements.

Once you have a method, as above, for obtaining the correct answer, it can obviously be used to evaluate any alternative method.

回答2:

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...