CODEWITHSUNDEEP
algorithmsortingcorrectness
Khoj Badami
Khoj Badami

Reputation: 191

Correctness Of Minimum Number Of Swaps To Sort An Array

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?

Upvotes: 2

Views: 3178

Answers (3)

sauravshah31
sauravshah31

Reputation: 91

If there is a element that is not in the correct position, then there must also be another element that is also not in it's correct position (the first element need to be placed in some other position that is occupied by another element). If this is represented in the form of a graph, the positions that don't have correct elements will have one edge towards it and on edge from it. This will end up forming one or more cycles. Now, the positions of the elements in the cycle are all within that cycle. So, we now need to prove that if there are 'n' elements in a cycle, minimum 'n-1' swaps are needed to sort them. We can prove this be induction.

Base: n=1
Only one element, so already sorted (trivial). This means 0 swaps, ie, n-1 => 1-1 = 0

Assume if there are k elements in a cycle, it takes min k-1 swaps

k+1 elements
A element in a cycle is has an edge towards the position that it need to be. This position has another edge towards some other position. Now, if we swap the former element, we are removing the former edge and the latter element goes to the swapped position. Now we are left with a cycle of size (k+1)-1 = k. By induction, k cycle requires k-1 swaps. So, k+1 will require (k-1)+1 = k swaps. Initial cycle(k) After one swap (k)

Upvotes: 2

joop
joop

Reputation: 4523

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

Upvotes: 0

ROX
ROX

Reputation: 1266

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.

Upvotes: 0

Related Questions