Minimum Swaps Required to Sort an Array
An efficient algorithm to find the minimum number of swaps required to sort the array in ascending order.
Problem:
We have an unordered array consisting of consecutive distinct integers ∈ [1,2,3,...n], where n is the size of the array.
We are allowed to swap any two elements.
We need to find the minimum number of swaps required to sort the array in ascending order.
Algorithm Concept:
1. Look at each index and compare the index position with its element value if its same then move to the next index position.
2. If index position is not the same as element value then treat element value as index value for finding the next element.
3. If we come back to the visited element then there exist a cycle, then count the size of that cycle, the number of swaps for particular cycle would be size-1, do this for all the cycles and add them together.
Outline (check the comment section for a clickable version):
00:00 : Introduction
00:06 : Problem
00:52 : Wrong Approach (Brute Force) Method with Animation Example
01:31 : Algorithm Concept
02:23 : Efficient Solution with Animation Example
05:44 : Code Implementation of Algorithm
Code Available At:
sites.google.com/view/minswaps
Пікірлер: 32
Minimum Swaps Required to Sort an Array [Non-Consecutive Distinct Integers] : kzread.info/dash/bejne/aoypw6ywgZW2Zc4.html
@PradeepKumar-ue2ct
3 жыл бұрын
Can you please mention time complexity of this solution?
@DSAlgo
3 жыл бұрын
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).
Great!! You have Explained well and implemented optimal solution
Helpful and clear. Thanks !
Really very effective approach to reduce swap counts.the way of explaining is very good and understandable. Thankyou so much.
Thanks for the explanation.
Nice Explanation!
Awesome. Very nicely and clearly explained !!
Thanxx.. I really enjoyed the way you explained the concept.
Very good explanation. Looking forward to more videos.
gr8 video!! make more videos for common problems
Your handwriting is so good
Awesome, keep it up 👍😇
this will only work for non duplicate values. nevertheless good work
@SudhanshuKumar-lp1nr
3 жыл бұрын
yes it's always distinct elements
Nice Content with gud explanation 👍
I understand the logic can someone explain why this works?
@MaXxamillion00
4 жыл бұрын
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.
Anyone have python code
pretty simple explanation
nice
Your handwriting is awesome😁😂
The explanation is AWESOME but the code is broken. could you please check it
@DSAlgo
4 жыл бұрын
Thanks Mohamed, The code is working fine and code link is available in the description.
@Anubis10110
4 жыл бұрын
@@DSAlgo Thanks I will check it..It's appearing now.
We can use selection sort which always takes least no. of swappings to sort an array. In the given array selection sort will take 1 swapping only.
@DSAlgo
3 жыл бұрын
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] kzread.info/dash/bejne/aoypw6ywgZW2Zc4.html - Selection sort algorithm approach.