Problem
We are given an array A of distinct integers that is not necessarily sorted. To sort the array, we are only allowed to do the below operation.
Find the number of these operations needed to sort any given array A of size n. Here n lies between 1 and 10000.
Operation
We have to pick the smallest possible index i in A such that there exists an index j and j>i and A[j]<A[i]. For that picked smallest i, if there are multiple valid j, pick the smallest possible j. Then swap the picked i and j.
Example
A={3,5,2,1,4}
Applying the given operations, below is the states of the array at each operation.
{3,5,2,1,4}–>{2,5,3,1,4}–>{1,5,3,2,4}–>{1,3,5,2,4}–>{1,2,5,3,4}–>{1,2,3,5,4}–>{1,2,3,4,5}.
So, the operations needed to sort {3,5,2,1,4} are 6.
P.S. - I was able to come up with an O(n^2) solution. Is there a better time complexity to solve this problem?
UPDATE
Was able to find an O(nlogn) solution.