minimum number of swaps required to sort the given input array = no. of
inveresions in the array
No. of inversions in the array is defined as no. of pairs (i,j) such that
a[i] > a[j] && i<j.
So, now we have to count the total inversions in the array :-
Since there are only 0 and 1. It can be done in linear time.
Algo :-
1:- Keep a pointer to the first element of the array . Initialise
one_count as zero.
2:- If the element is zero, then inversion_count += one_count.
Else if the element is one , one_count ++;
Finally, inversion_count contains the answer.
Time Complexity :- O(n) as single traversal is needed.
Space Complexity :- O(1) constant space required.
--
Navin Kumar Gupta
Final Year,B.Tech(Hons.)
Computer Science & Engg.
National Institute of Technology,Jamshedpur
Mobile - (+91)8285303045
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/44gDXly-hq0J.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
