Time complexity to find the minimum swaps is mentioned below: i. Using Efficient algorithm is O(n log(n)). ii. Using Selection sort algorithm is O(n^2).
This works this way because this case is somewhat unique: all elements in the array are unique, and once sorted, all element values match their corresponding indices.... as in 1 is in position 1, 2 will be in position 2, 4 in 4, etc. That is why you can find one element out of place(because index!=value) and immediately jump to the place it SHOULD BE (index==value), and do the same thing with the out-of-place element found there. Eventually you will find the element that belongs to the initial index you were checking, the first out-of-place element, and that whole series of elements becomes a "cycle", you can perform an exact finite series of swaps to get all of those elements into their corresponding indices... like the video describes haha but long story short it works this way because in this array, once sorted, index==element for all indices.
Thanks for suggestion, The selection sort algorithm is not an efficient solution for this problem. Please see the explanation below: The selection sort algorithm is a brute force approach i.e. more computational effort is required. Therefore, It is not an optimal solution for finding the minimum swaps required to sort an unordered array consisting of consecutive distinct integers ∈ [1,2,3,...n]. e.g. [4,3,2,1] [1,5,4,3,2] We can use the selection sort algorithm for unordered array consisting of distinct integers ∈ Z i.e. {..., -2, -1, 0, 1, 2, ...}. e.g. [2,4,1,5] [4, 10, 2, 1, 0] ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-8XuaJwQ2P5k.html - Selection sort algorithm approach.
