1

I'am given an unsorted array. Need to find minimum number of swaps to sort it. I already encountered some advices on the issue here: discussion

But there is no strict proof of the proposed algorithm.

voipp
  • 1,243
  • 3
  • 18
  • 31
  • This is not the place for this kind of question. The proof has more to do with math than coding. If you want *strict proof* you should take it to a different stack exchange site. – IcedLance Jun 19 '19 at 10:19
  • 1
    But basically you organize elements into shift groups (abcde->bcdea) and shift group of N elements cant be shifted without N-1 swaps and swap order isnt important as long as they are correct and the proposed algorithm basically does those swaps within shift groups and if you can do it faster then you can shift one of the shift groups in N-2 which is impossible. That is as strict as you gonna get here. – IcedLance Jun 19 '19 at 10:33
  • 1
    Oh, only theres an issue with identical elements that would require more careful consideration, but the main idea is the same. – IcedLance Jun 19 '19 at 10:39
  • @IcedLance thanks will think over it on my leisure time – voipp Jun 19 '19 at 11:24
  • Are the elements in your array also distinct? – Bernhard Barker Jun 19 '19 at 12:03
  • @Dukeling yes they are – voipp Jun 19 '19 at 12:04

0 Answers0